记录编号	23693	评测结果	AAAAAAAAAA
题目名称	Brownie Slicing	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.670 s
提交时间	2011-03-17 14:53:14	内存使用	4.09 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

long long sum[501][501];
long long map[501][501];
long long maxsum;
int N,M,A,B;
void init()
{
	scanf("%d%d%d%d",&N,&M,&A,&B);
	for (int i=1;i<=N;i++)
	for (int j=1;j<=M;j++)
	{
		scanf("%lld",&map[i][j]);
		maxsum+=map[i][j];
		sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j];
	}
}

inline long long area(int xi1,int yi1,int xi2,int yi2)
{
	return sum[xi2][yi2]-sum[xi1-1][yi2]-sum[xi2][yi1-1]+sum[xi1-1][yi1-1];
}

bool can(long long lim,int xi1,int xi2)
{
	int yi1=1,yi2=1,ans=0;
	while (yi2<=M)
	{
		while (area(xi1,yi1,xi2,yi2)<lim && yi2<=M) yi2++;
		if (yi2<=M)
		{
			ans++;
			if (ans>=B) return true;
			yi2=yi1=yi2+1;
		}
	}
	return (ans>=B);
}

bool cul(long long lim)
{
	int xi1=1,xi2=1,ans=0;
	while (xi2<=N)
	{
		while (!can(lim,xi1,xi2) && xi2<=N) xi2++;
		if (xi2<=N)
		{	
			ans++;
			if (ans>=A) return true;
			xi2=xi1=xi2+1;
		}
	}
	return (ans>=A);
}

void solve()
{
	long long L=0,R=maxsum,mid;
	while (L<R)
	{
		mid=(L+R+1)/2;
		if (cul(mid)) L=mid;
		else R=mid-1;
	}
	printf("%lld\n",L);
}

int main()
{
	freopen("brownie.in","r",stdin);
	freopen("brownie.out","w",stdout);
	init();
	solve();
	return 0;
}