Cod sursa(job #826677)

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

long long v[305][305];
long long w[305];

bool isok (long long ans)
{
	for(int a=0;a<n;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);
			}

			deque<long long> d;
			if(w[c-1]>=0)
				return 1;
			for(int i=c;i<m;i++){
				while(d.empty()==false&&w[d.back()]>=w[i-c])
					d.pop_back();
				d.push_back (i-c);
				while(d.empty()==false&&d.front()<i-m/2+1)
					d.pop_front();
				if(!d.empty()&&w[i]-w[d.front()]>=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;
}