Cod sursa(job #826679)

Utilizator Marius96Marius Gavrilescu Marius96 Data 1 decembrie 2012 01:15:44
Problema Balans Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>
#include<deque>
using std::deque;
int n,m,r,c;

long long v[305][305];
long long w[305];
long long d[305];
int df;
int db;

bool isok (long long ans)
{
	for(int a=0;a<n/2;a++)
		for(int b=a+r-1;b<n&&b-a+1<=n/2;b++){
			w[0]=0;
			for(int i=0;i<m;i++){
				if(i)
					w[i]=w[i-1];
				w[i]+=v[b][i]*1000;
				if(a)
					w[i]-=v[a-1][i]*1000;
				w[i]-=ans*(b-a+1);
			}

			df=1,db=0;
			if(w[c-1]>=0)
				return 1;
			for(int i=c;i<m;i++){
				while(df<=db&&w[d[db]]>=w[i-c])
					db--;
				d[++db]=i-c;
				while(df<=db&&d[df]<i-m/2+1)
					df++;
				if(df<=db&&w[i]-w[d[df]]>=0)
					return 1;
			}
		}

	return 0;
}

int main (void)
{
	freopen ("balans.in","r",stdin);
#ifdef INFOARENA
	freopen ("balans.out","w",stdout);
#endif

	scanf ("%d%d%d%d",&n,&m,&r,&c);

	if(!r)
		r=1;
	if(!c)
		c=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf ("%d",v[i]+j);

	for(int i=0;i<2*n;i++)
		for(int j=0;j<2*m;j++)
			v[i][j]=v[i%n][j%m];
	n*=2;
	m*=2;

	for(int i=1;i<n;i++)
		for(int j=0;j<n;j++)
			v[i][j]+=v[i-1][j];

	isok (1889);
	long long s=1,e=1000000000;
	while(s<e){
		int m=(s+e)/2;
		if(m==s)
			m=e;

		if(isok (m))
			s=m;
		else
			e=m-1;
	}

	printf ("%d.%03d",s/1000,s%1000);
	return 0;
}