YbtOj练习：二分4 分割矩阵

http://noip.ybtoj.com.cn/contest/15/problem/4

这道题其实就是   数组分段的二维拓展，但是它求的是最大的最小值

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,A,B;
int g[N][N],sum[N][N],l,r;
bool f(int L,int r,int x)
{
    int cnt=0,S=0;
    for(int j=1;j<=m;j++)
    {
        S+=sum[r][j]-sum[L-1][j];
        if(S>=x)
        {
            cnt++;
            S=0;
        }
    }
    if(cnt<B) return false;
    return true;
}
bool check(int x)
{
    int cnt=0,L=1;
    for(int i=1;i<=n;i++)
    {
        if(f(L,i,x))
        {
            cnt++;
            L=i+1;
        }
    }
    if(cnt<A) return false;
    return true;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&A,&B);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      {
          scanf("%d",&g[i][j]);
          sum[i][j]=sum[i-1][j]+g[i][j];
      }
    for(int j=1;j<=m;j++) r+=sum[n][j];
    while(l<r)
    {
        
        int mid=l+r+1>>1;
        if(!check(mid)) r=mid-1;
        else l=mid;
    }
    printf("%d",l);
    return 0;
}

 目前尚不清楚为什么cnt从0开始。。。之前都是从1开始的