Pagini recente » Cod sursa (job #2989041) | Cod sursa (job #646638) | Cod sursa (job #2582540) | Cod sursa (job #303237) | Cod sursa (job #826678)
Cod sursa(job #826678)
#include<cstdio>
#include<deque>
using std::deque;
int n,m,r,c;
long long v[305][305];
long long w[305];
bool isok (long long ans)
{
for(int a=0;a<n;a++)
for(int b=a+r-1;b<n&&b-a+1<=n/2;b++){
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);
}
deque<long long> d;
if(w[c-1]>=0)
return 1;
for(int i=c;i<m;i++){
while(d.empty()==false&&w[d.back()]>=w[i-c])
d.pop_back();
d.push_back (i-c);
while(d.empty()==false&&d.front()<i-m/2+1)
d.pop_front();
if(!d.empty()&&w[i]-w[d.front()]>=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<n;j++)
v[i][j]+=v[i-1][j];
isok (1889);
long long s=1,e=1000000000;
while(s<e){
int m=(s+e)/2;
if(m==s)
m=e;
if(isok (m))
s=m;
else
e=m-1;
}
printf ("%d.%03d",s/1000,s%1000);
return 0;
}