Cod sursa(job #999575)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 20 septembrie 2013 20:29:16
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include<fstream>
#include<cstdio>
#include<deque>
#define LG 8000000
using namespace std;
int n,m,n2,m2,R,C,mat[310][310],ind;
long long sumC[310][310];
char buffer[LG];

inline void Citeste(int &x)
{
    while(buffer[ind]<'0' || '9'<buffer[ind])
    {
        ind++;
        if(ind==LG)
        {
            fread(buffer,1,LG,stdin);
            ind=0;
        }
    }
    x=0;
    while('0'<=buffer[ind] && buffer[ind]<='9')
    {
        x=x*10+buffer[ind]-'0';
        ind++;
        if(ind==LG)
        {
            fread(buffer,1,LG,stdin);
            ind=0;
        }
    }
}

inline bool Posibil(int X)
{
	int i,j,k,sz=0;
	long long best=-10000000000000000LL,sum[310];
	deque <int> D;
	for(i=1;i<=n;i++)
	{
		for(k=i+R-1;k-i+1<=n2 && k<=n;k++)
		{
			sum[0]=0;
			for(j=1;j<=m;j++)
				sum[j]=sum[j-1]+sumC[k][j]-sumC[i-1][j]-1LL*X*(k-i+1);
			D.clear();
			sz=0;
			for(j=C;j<=m;j++)
			{
				while(sz && sum[D.back()]>=sum[j-C])
				{
					sz--;
					D.pop_back();
				}
				D.push_back(j-C);
				sz++;
				while(D.front()<j-m2)
				{
					sz--;
					D.pop_front();
				}
				best=max(best,sum[j]-sum[D.front()]);
			}
			if(best>=0)
				return true;
		}
	}
	return false;
}

inline int CautareBinara()
{
	int st,dr,mij,rez=0;
	st=0;
	dr=100000000;
	if(R==0 || C==0)
		return 0;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(Posibil(mij))
		{
			rez=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	}
	return rez;
}

int main()
{
	int i,j;
	freopen("balans.in","r",stdin);
    fread(buffer,1,LG,stdin);
	
	Citeste(n); Citeste(m); Citeste(R); Citeste(C);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			Citeste(mat[i][j]);
			mat[i][j]*=1000;
			mat[i+n][j]=mat[i][j+m]=mat[i+n][j+m]=mat[i][j];
		}
	}
	n2=n;
	m2=m;
	n*=2;
	m*=2;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			sumC[i][j]=sumC[i-1][j]+1LL*mat[i][j];
	
	freopen("balans.out","w",stdout);
	printf("%.3lf\n",(1.0*CautareBinara())/1000.0);
	return 0;
}