Pagini recente » Cod sursa (job #1121472) | Cod sursa (job #2760033) | Cod sursa (job #2856941) | Istoria paginii runda/winners13 | Cod sursa (job #1720607)
#include <iostream>
#include<fstream>
#include<iomanip>
using namespace std;
const int en=155;
long long minim[2*en],deq[en],d[en],a[en][en],s[2*en][2*en],el;
int i,j,n,m,k,newi,newj,N,M,u,p,r,c,i1,j1;
long long pr,ul,em,mx,sum;
bool rez;
void build(long long x)
{
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
{
newi=i;newj=j;
if(newi>n) newi-=n;
if(newj>m) newj-=m;
s[i][j]=s[i-1][j]+a[newi][newj]-x;
}
}
bool check(long long x)
{
build(x);
for(i=r;i<=N;i++)
for(i1=max(0,i-n);i1<=i-r;i1++)
{
p=0;u=0;
el=0;
for(j=1;j<=M;j++)
{
el+=s[i][j]-s[i1][j];
if(i-d[p]>=k+1) p++;
while(el<=deq[u]&&p<=u)
u--;
u++;
deq[u]=el;
d[u]=j;
minim[j]=deq[u];
if(j<=k&&0<minim[j]) minim[j]=0;
if(k==0) minim[j]=el;
if(j>=c)
{
if(el-minim[j-c]>=0) return true;
}
}
}
return false;
}
void rezolvabrut()
{
build(0);
for(i=1;i<=N;i++)
for(i1=max(0,i-n);i1<=i-r;i1++)
{
for(j=1;j<=M;j++)
{
sum=0;
for(j1=max(0,j-m);j1<=j-c;j1++)
{
sum+=s[i][j1]-s[i1][j1];
if(i!=i1&&j!=j1)
if(sum/((i1-i)*(j1-j))>ul)
{
ul=sum/((i1-i)*(j1-j));
}
}
}
}
}
int main()
{
ifstream f("balans.in");
ofstream g("balans.out");
f>>n>>m>>r>>c;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{f>>a[i][j];a[i][j]*=10000;}
pr=0;ul=1000000000;
N=2*n;M=2*m;
k=m-c;
bool ok;
//if(r==0||c==0) {ul=0;rezolvabrut();ok=1;}
//else
while(ul-pr>1)
{
em=(pr+ul)/2;
if(check(em)) pr=em;
else ul=em;
}
if(ok==0)
if(!check(ul)) ul--;
double rasp=ul;
rasp/=10000;
g<<fixed<<setprecision(3)<<rasp;
return 0;
}