Cod sursa(job #481931)

Utilizator indestructiblecont de teste indestructible Data 1 septembrie 2010 23:23:27
Problema Balans Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#define NMAX 301
#define ll long long
int n,m,r,c;
int A[NMAX][NMAX],rez;
int deq[NMAX],inc,sf;
ll B[NMAX][NMAX],S2[NMAX],S[NMAX][NMAX],act;
char possible;
void read()
{
	scanf("%d%d%d%d",&n,&m,&r,&c);
	int i,j;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=m; j++)
		{
			scanf("%d",&A[i][j]);
			A[i][j]*=10000;
		}
		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];
}
void actualizare(int i)
{
	while (inc!=sf && S2[deq[sf-1]]>=S2[i])
		sf--;
	deq[sf++]=i;
}
void capat_st(int i)
{
	if (i-deq[inc]>m)
		inc++;
}
inline int ok(int x)
{
	int i,j,k;
	possible=0;
	for (i=1; i<=2*n; i++)
		for (j=1; j<=2*m; j++)
		{
			B[i][j]=A[i][j]-x;
			S[i][j]=S[i-1][j]+B[i][j];
			if (S[i][j]>0)
				possible=1;
		}
	if (!possible)
		return 0;
	for (j=1; j<=2*n; j++)
		for (k=j+r-1; k<=2*n && k-j<n; k++)
		{
			inc=sf=0;
			for (i=1; i<=2*m; i++)
			{
				S2[i]=S2[i-1]+S[k][i]-S[j-1][i];
				if (i>=c)
				{
					actualizare(i-c);
					capat_st(i);
					act=S2[i]-S2[deq[inc]];
					if (act>=0)
						return 1;
				}
			}
		}
	return 0;
}
inline int cbin()
{
	int i,step=(1<<30);
	for (i=0; step; step>>=1)
		if (ok(i+step))
			i+=step;
	return i;
}
int main()
{
	freopen("balans.in","r",stdin);
	freopen("balans.out","w",stdout);
	read();
	rez=cbin();
	printf("%d.%d\n",rez/10000,rez%10000/10);
	return 0;
}