Pagini recente » Cod sursa (job #2923227) | Cod sursa (job #2876526) | Cod sursa (job #2166123) | Cod sursa (job #3169588) | Cod sursa (job #826681)
Cod sursa(job #826681)
#include<cstdio>
#include<deque>
using std::deque;
int n,m,r,c;
long long v[305][305];
long long w[305];
long long d[305];
int df;
int db;
bool isok (int a, int b, long long ans)
{
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);
}
df=1,db=0;
if(w[c-1]>=0)
return 1;
for(int i=c;i<m;i++){
while(df<=db&&w[d[db]]>=w[i-c])
db--;
d[++db]=i-c;
while(df<=db&&d[df]<i-m/2+1)
df++;
if(df<=db&&w[i]-w[d[df]]>=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<m;j++)
v[i][j]+=v[i-1][j];
long long s=1,e=1000000000;
for(int a=0;a<n/2;a++)
for(int b=a+r-1;b<n&&b-a+1<=n/2;b++){
e=1000000000;
if(!isok (a,b,s))
continue;
while(s<e){
int m=(s+e)/2;
if(m==s)
m=e;
if(isok (a,b,m))
s=m;
else
e=m-1;
}
}
printf ("%d.%03d",s/1000,s%1000);
return 0;
}