Cod sursa(job #999465)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 20 septembrie 2013 15:09:21
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<fstream>
#include<cstdio>
#include<deque>
using namespace std;
int n,m,R,C,mat[310][310];
int M[310][310],sum[310],sumC[310][310];
deque <int> D;

inline bool Posibil(int X)
{
	int i,j,k,best=-1000000000;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			M[i][j]=1000*mat[i][j]-X;
			sumC[i][j]=sumC[i-1][j]+M[i][j];
		}
	}
	for(i=1;i<=n;i++)
	{
		for(k=i+R-1;k<=n;k++)
		{
			if(k-i+1>n/2)
				continue;
			sum[0]=0;
			for(j=1;j<=m;j++)
				sum[j]=sum[j-1]+sumC[k][j]-sumC[i-1][j];
			D.clear();
			for(j=C;j<=m;j++)
			{
				while(D.size() && sum[D.back()]>=sum[j-C])
					D.pop_back();
				D.push_back(j-C);
				while(D.front()<j-m/2)
					D.pop_front();
				best=max(best,sum[j]-sum[D.front()]);
			}
		}
	}
	if(best>=0)
		return true;
	return false;
}

inline double CautareBinara()
{
	int st,dr,mij,rez=0;
	st=0;
	dr=100000000;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(Posibil(mij))
		{
			rez=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	}
	return (1.0*rez)/1000.0;
}

int main()
{
	int i,j;
	ifstream fin("balans.in");
	fin>>n>>m>>R>>C;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			fin>>mat[i][j];
			mat[i+n][j]=mat[i][j+m]=mat[i+n][j+m]=mat[i][j];
		}
	}
	n*=2;
	m*=2;
	fin.close();
	
	freopen("balans.out","w",stdout);
	printf("%.3lf\n",CautareBinara());
	return 0;
}