Cod sursa(job #541142)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 24 februarie 2011 20:56:45
Problema Balans Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <cmath>
#define nmax 310
#define X 1000

int st, dr, sol;
int a[nmax][nmax], n, m, r, c, p[nmax];
long long b[nmax][nmax], s[nmax][nmax], v[nmax], q[nmax];

int verif(int x)
{
	int i, j, st, dr, y, i1, i2;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) b[i][j]=a[i][j]*X-x;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) 
			s[i][j]=s[i-1][j]+b[i][j];
	for (i1=1; i1<=n; i1++)
		for (i2=i1+r-1; i2<=n && i1+n/2>i2; i2++)
		{
			for (j=1; j<=m; j++) v[j]=v[j-1]+s[i2][j]-s[i1-1][j];
			st=1;
			dr=0;
			if (v[c]>=0) return 1;
			y=c+1;
			for (j=1; y<=m; j++, y++)
			{
				while (v[j]<q[dr] && st<=dr) dr--;
				while (p[st]+m/2<=y && st<=dr) st++;
				dr++;
				q[dr]=v[j];
				p[dr]=j;
				if (v[y]>=q[st]) return 1;
			}
		}
	return 0;
}

int main()
{
	freopen("balans.in","r",stdin);
	freopen("balans.out","w",stdout);
	scanf("%d %d %d %d",&n, &m, &r, &c);
	int i, j, mij;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) scanf("%d",&a[i][j]);
	st=1<<30;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			a[i+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
			if (a[i][j]<st) st=a[i][j];
			if (a[i][j]>dr) dr=a[i][j];
		}
	n*=2;
	m*=2;
	st*=X;
	dr*=X;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (verif(mij))
		{
			st=mij+1;
			sol=mij;
		} else dr=mij-1;
	}
	i=sol%X;
	printf("%d.%d",sol/X, i);
	if (!i) printf("000\n"); else
	if (i<10) printf("00\n"); else 
	if (i<100) printf("0\n"); else printf("\n");
}