Cod sursa(job #541125)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 24 februarie 2011 20:47:38
Problema Balans Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <cmath>
#define nmax 310
#define eps 0.001

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

int verif(double x)
{
	int i, j, st, dr, y, i1, i2;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) b[i][j]=(double) a[i][j]-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;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) scanf("%d",&a[i][j]);
	double mij;
	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;
	while (fabs(st-dr)>eps)
	{
		mij=(st+dr)/2;
		if (verif(mij))
		{
			st=mij;
			sol=mij;
		} else dr=mij;
	}
	printf("%.3lf\n",sol);
}