分割矩陣 (二分范圍[L,R)）

  分割矩陣
                   (browine.c/cpp/pas)
【問題描述】
    有N*M的一個非負整數矩陣。現在要把矩陣分成A*B塊。矩陣先水平地切A-1刀，把矩陣劃分成A塊。然後再把剩下來的每一塊獨立地切豎著B-1刀。每塊的價值為塊上的數字和。求一種方案，使得最小價值塊的價值最大。
【輸入格式】
    第一行四個整數N,M,A,B。
    接下來N行，每行M個非負整數。代表這個矩陣
【輸出格式】
    一個數字。最小價值塊的價值。
【樣例輸入】
5 4 4 2
1 2 21
3 1 1 1
2 0 1 3
1 1 1 1
1 1 11
【樣例輸出】
    3
 
樣例解釋見圖片
【數據規模】
   1<=A<=N<=500
   1<=B<=M<=500
    其他數字小於4000。
 
 二分的同志請注意了
m=(l+r)/2 <-----這句是永遠也枚不到L與R的

[cpp]
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<cstdlib> 
#include<iostream> 
#include<functional> 
#include<algorithm> 
using namespace std; 
#define MAXN (500+10) 
#define MAXM (500+10) 
#define MAXT (2000000+10) 
int n,m,t1,t2,a[MAXN][MAXM],sum[MAXN][MAXM]={0}; 
bool is_ok(int l,int r,int _m) 
{ 
    int tot=0,p=0; 
    for (int i=1;i<=m;i++) 
    { 
        tot+=sum[r][i]-sum[l-1][i]; 
        if (tot>=_m) {tot=0;p++;} 
    } 
    if (p>=t2) return 1; 
    else return 0; 
} 
bool is_ok_(int _m) 
{ 
    int p=0,l=1; 
    for (int i=1;i<=n;i++) 
    { 
        if (is_ok(l,i,_m)) {l=i+1;p++;} 
    } 
    if (p>=t1) return 1; 
    else return 0; 
} 
int main() 
{ 
    freopen("browine.in","r",stdin); 
    freopen("browine.out","w",stdout); 
    scanf("%d%d%d%d",&n,&m,&t1,&t2); 
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=m;j++) 
        { 
            scanf("%d",&a[i][j]); 
            sum[i][j]=sum[i-1][j]+a[i][j]; 
        } 
    /*
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            printf("%d ",sum[i][j]);
        }
    */ 
//  cout<<(is_ok_(4)); 
    int l=1,r=1,ans=0; 
    for (int j=1;j<=m;j++) r+=sum[n][j]; 
     
    for (int i=1;i<=60;i++) 
    { 
        int m_=(l+r)/2; 
        if (is_ok_(m_)) {l=ans=m_;} 
        else r=m_;               
    } 
    printf("%d\n",ans); 
         
//  while (1); 
    return 0; 
}