Cod sursa(job #2333691)

Utilizator patcasrarespatcas rares danut patcasrares Data 1 februarie 2019 19:51:56
Problema Balans Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int DN=305;
int m,n,l,u;
int R,C;
int st,dr,mij;
long long sum[DN],val,sol,t;
double rez;
long long b[DN][DN];
pair<long long,long long>a[DN];
pair<long long,int>d[DN];
int vf(double z)
{
	for(int i=1;i<=n;i++)
	{
		val=a[i].x-a[i].y*z;
		sum[i]=sum[i-1]+val;
	}
	int ds=1,dr=0;
	for(int i=1;i<=n;i++)
	{
		if(i>=l)
		{
			while(1)
			{
				if(ds>dr)
					break;
				if(sum[i-l]>d[dr].x)
					break;
				dr--;
			}
			dr++;
			d[dr]={sum[i-l],i};
		}
		while(1)
			{
				if(ds>dr)
					break;
				if(d[ds].y>=i-u)
					break;
				ds++;
			}
		if(ds<=dr)
			if(sum[i]-d[ds].x>0)
				return 1;
	}
	return 0;
}
int main()
{
	fin>>m>>n;
	fin>>R>>C;
	if(R==0)
        R=1;
    if(C==0)
        C=1;
	l=C;
	u=n;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>b[i][j];
			b[i][j]*=1000;
		}
	for(int i=1;i<=m;i++)
		for(int j=n+1;j<=2*n;j++)
			b[i][j]=b[i][j-n];
	n*=2;
	for(int i=m+1;i<=2*m;i++)
		for(int j=1;j<=n;j++)
			b[i][j]=b[i-m][j];
	m*=2;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			b[i][j]+=b[i-1][j];
	for(int i1=1;i1<=m/2;i1++)
		for(int i2=i1+R-1;i2<=min(m,i1-1+m/2);i2++)
		{
			for(int i=1;i<=n;i++)
			{
				a[i].y=1;
				a[i].x=b[i2][i]-b[i1-1][i];
				a[i].x/=i2-i1+1;
			}
			st=sol;
			if(!vf(sol))
                continue;
			dr=1e8;
			while(st<dr)
			{
				mij=(st+dr+1)/2;
				t=mij;
				if(vf(t))
					st=mij;
				else
					dr=mij-1;
			}
			//st++;
            t=st;
			sol=max(sol,t);
		}
	rez=sol+1;
	rez/=1000;
	fout<<fixed<<setprecision(3)<<rez;
}