Problem C.星际争霸

For Aiur

Input file	aiur.in
Output file	aiur.out
Time limit	1 sec
Memory limit	128 mb

 

 

不知道比你们高到哪里去的Liang，昨天率领他的无敌黄金舰队高喊着“For Aiur”闯入虫族大本营，打退了虫族，为Aiur星球续了1秒，光影议会的大主教感觉Liang同学十分厉害就钦定了他当Aiur特首。

这势必要进行庆祝，于是庆祝专用蛋糕就这样诞生了，这是一块矩形蛋糕，它由 N M 个小蛋糕组成，每个蛋糕的美味指数为 T_ij 。

为了把蛋糕分给其他指挥官，Liang决定横着切 A-1 刀，再把得到的A块各竖着切 B-1 刀，分成 B 块，这样一共有A*B 块。为了使大家都高兴，能和他谈笑风生，他希望让美味指数之和最少的那个蛋糕的美味指数最大。请你告诉他这个值吧。注意，你不能把小蛋糕切碎。（告诉你们个大新闻，Liang的黄金舰队被BUFF的大和炮轰个稀巴烂）

 

Input

 

输入第一行四个数 N; M; A;B接下来 N 行，每行 M 个整数数。

 

Output

 

 

输出一个整数，为答案。

Examples

 

aiur.in	aiur.out
5 4 4 2   1 2 2 1   3 1 1 1   2 0 1 3   1 1 1 1   1 1 1 1	3

 

Hint

 

对于 100% 的数据，有 1<=N; M<=500; 0<=T_ij<=4000; 1<=A<=N; 1<=B<=M。

 

 

 

1	2	2	1
3	1	1	1
2	0	1	3
1	1	1	1
1	1	1	1

 

饿分题，嗯

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include "algorithm"10 using namespace std;11 typedef long long LL;12 const int MAX=505;13 int n,m,A,B;14 int s[MAX][MAX];15 void init(){16 int i,j,k;17 scanf("%d%d%d%d",&n,&m,&A,&B);18 memset(s,0,sizeof(s));19 for (i=1;i<=n;i++){20 for (j=1;j<=m;j++){21 scanf("%d",&k);22 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+k;23 }24 }25 }26 int squ(int x,int y,int a,int b){27 return s[x][y]-s[a][y]-s[x][b]+s[a][b];28 }29 bool feasible(int x){30 int i,j,last1=0,last2;31 int a=0,b;32 for (i=1;i<=n;i++){33 b=0;34 last2=0;35 for (j=1;j<=m;j++){36 if (squ(i,j,last1,last2)>=x){37 b++;38 last2=j;39 }40 }41 if (b>=B) a++,last1=i;42 }43 return (a>=A);44 }45 int main(){46 freopen ("aiur.in","r",stdin);47 freopen ("aiur.out","w",stdout);48 init();int i,j;49 int low,high,mid;50 low=1,high=s[n][m]/(A*B);51 while (low<=high){52 mid=(low+high)>>1;53 if (feasible(mid))54 low=mid+1;55 else 56 high=mid-1;57 }58 printf("%d",low-1);59 return 0;60 }