description

今天是Bessie的生日,他买了一个蛋糕和朋友们一起分享,蛋糕可以看成是一个R行C列的表格,共有R*C个格子,每个格子都有一个0至9的数字,表示该格子蛋糕拥有的巧克力。现在Bessie要把蛋糕横的切3刀再竖的切3刀,由于Bessie刀法厉害,所以每个格子蛋糕都是完整的,显然蛋糕会被切成16份,然后Bessie和他的15个朋友们每人拿一份,Bessie比较客气,总是等其他朋友拿完了,Bessie拿最后剩下的那一份。Bessie的朋友们都很不客气,都是挑最多巧克力的那份去拿,于是Bessie最后拿到手的那份蛋糕总是巧克力总和最少的。Bessie心想:既然自己总是最后拿蛋糕,那应该怎么切蛋糕,才能使得自己拿的那部分蛋糕的有尽量多的巧克力呢?这个问题自然是你的任务了。


analysis

  • 要求最大值最小,先二分一个答案

  • 对于竖行,\(O(n^3)\)枚举切哪三列,然后剩下用三个二分找出可以满足条件的最小矩形

  • 如果十六个矩形的和的最小值都大于二分的答案则可以把答案取大,否则取小

  • 时间复杂度\(O(n^3log^2n)\)


code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 105
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll a[MAXN][MAXN],sum[MAXN][MAXN];
ll n,m,num;

inline ll get(ll x,ll y,ll xx,ll yy){return sum[xx][yy]-sum[x-1][yy]-sum[xx][y-1]+sum[x-1][y-1];}
inline bool judge(ll x)
{
    fo(i,1,m-1)fo(j,i+1,m-1)fo(k,j+1,m-1)
    {
        ll l=1,r=n,mid,las;
        while (l<r)mid=(l+r)>>1,min(min(get(1,1,mid,i),get(1,i+1,mid,j)),min(get(1,j+1,mid,k),get(1,k+1,mid,m)))>=x?r=mid:l=mid+1;
        if (!r)continue;

        las=l=r+1,r=n;
        while (l<r)mid=(l+r)>>1,min(min(get(las,1,mid,i),get(las,i+1,mid,j)),min(get(las,j+1,mid,k),get(las,k+1,mid,m)))>=x?r=mid:l=mid+1;
        if (r<las)continue;

        las=l=r+1,r=n;
        while (l<r)mid=(l+r)>>1,min(min(get(las,1,mid,i),get(las,i+1,mid,j)),min(get(las,j+1,mid,k),get(las,k+1,mid,m)))>=x?r=mid:l=mid+1;
        if (r<las)continue;

        if (min(min(get(r+1,1,n,i),get(r+1,i+1,n,j)),min(get(r+1,j+1,n,k),get(r+1,k+1,n,m)))>=x)return 1;
    }
    return 0;
}
int main()
{
    //freopen("T1.in","r",stdin);
    scanf("%lld%lld\n",&n,&m);
    fo(i,1,n){fo(j,1,m)num+=(a[i][j]=getchar()-'0');scanf("\n");}
    fo(i,1,n)fo(j,1,m)sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    ll l=0,r=num/16,mid;
    while (l<=r)mid=(l+r)>>1,judge(mid)?l=mid+1:r=mid-1;
    printf("%lld\n",r);
    return 0;
}
12-14 04:28