记录编号	23785	评测结果	AAAAAAAAAA
题目名称	Brownie Slicing	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.455 s
提交时间	2011-03-20 14:09:41	内存使用	1.23 MiB

#include <cstdio>
#include <cstring>

const int MAXN=505;

int A,B,R,C;
int a[MAXN][MAXN];
int sum[MAXN];
bool judge(int mid)
{
	int na=0,ni=1;
	memset(sum,0,sizeof(sum));
	while(na<A&&ni<=R)
	{
		for(int i=1;i<=C;i++)
			sum[i]+=a[ni][i];
		int nb=0;
		for(int i=1,ns=0;i<=C&&nb<B;i++)
		{
			ns+=sum[i];
			if (ns>=mid) nb++,ns=0;
		}
		if (nb==B)
		{
			memset(sum,0,sizeof(sum));
			na++;
		}
		ni++;
	}
	return (na==A);
}

void solve()
{
	int l=0,r=2000000;
	while(l+1<r)
	{
		int mid=((long long)(l)+r)/2;
		if (judge(mid)) l=mid;
		else r=mid-1;
	}
	if (l==r) printf("%d\n",l);
	else if (judge(r)) printf("%d\n",r);
	else printf("%d\n",l);
}

int main()
{
	freopen("brownie.in","r",stdin);
	freopen("brownie.out","w",stdout);
	scanf("%d%d%d%d",&R,&C,&A,&B);
	for(int i=1;i<=R;i++)
		for(int j=1;j<=C;j++)
			scanf("%d",a[i]+j);
	solve();
	return 0;
}