Cod sursa(job #493397)

Utilizator indestructiblecont de teste indestructible Data 17 octombrie 2010 23:24:19
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#define NMAX 305
#define INF 2000000000
#define ll long long
int n,m,p,q,A[NMAX][NMAX],vmax;
ll S[NMAX][NMAX],C[NMAX],D[NMAX],E[NMAX];
void read()
{
	scanf("%d%d%d%d",&n,&m,&p,&q);
	int i,j;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=m; j++)
			scanf("%d",&A[i][j]);
		for (j=m+1; j<2*m; j++)
			A[i][j]=A[i][j-m];
	}
	for (i=n+1; i<2*n; i++)
		for (j=1; j<2*m; j++)
			A[i][j]=A[i-n][j];
	n=2*n-1; m=2*m-1;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			A[i][j]*=1000;
			if (A[i][j]>vmax) vmax=A[i][j];
			S[i][j]=S[i-1][j]+A[i][j];
		}
}
inline ll min(ll x,ll y)
{
	return x<y ? x : y;
}
inline ll max(ll x,ll y)
{
	return x>y ? x : y;
}
bool ok(int val)
{
	int i,j,k;
	ll best=-INF;
	for (i=1; i<=n-p+1; i++)
		for (j=i+p-1; j<=n; j++)
		{
			for (k=1; k<=m; k++)
				C[k]=(S[j][k]-S[i-1][k])-(ll)val*(j-i+1);
			for (k=1; k<=m; k++)
			{
				E[k]=E[k-1]+C[k];
				D[k]=min(D[k-1],E[k]);
				if (k>=q)
					best=max(best,E[k]-D[k-q]);
			}
			if (best>0)
				return 1;
		}
	return 0;
}
int cbin()
{
	int l,r,m,rez;
	for(l=0, r=vmax; l<=r; ){
		m=l+(r-l)/2;
		if( ok(m) ){
			rez=m;
			l=m+1;
		}
		else r=m-1;
	}
	return rez;
}
int main()
{
	freopen("balans.in","r",stdin);
	freopen("balans.out","w",stdout);
	read();
	int ans=cbin();
	printf("%.3lf\n",(double)ans/1000);
	return 0;
}