Cod sursa(job #826682)

Utilizator Marius96Marius Gavrilescu Marius96 Data 1 decembrie 2012 02:18:23
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 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 (int a, int b, long long ans)
{
	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 ("%lld",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<m;j++)
			v[i][j]+=v[i-1][j];

	long long s=1,e=1000000000;

	for(int a=0;a<n/2;a++)
		for(int b=a+r-1;b<n&&b-a+1<=n/2;b++){
			e=1000000000;
			if(!isok (a,b,s))
				continue;

			while(s<e){
				int m=(s+e)/2;
				if(m==s)
					m=e;

				if(isok (a,b,m))
					s=m;
				else
					e=m-1;
			}
		}
	
	printf ("%lld.%03lld",s/1000,s%1000);
	return 0;
}