Pagini recente » Cod sursa (job #2669765) | Cod sursa (job #1731456) | Cod sursa (job #2286934) | Cod sursa (job #2354898) | Cod sursa (job #2347914)
#include <iostream>
#include <cstdio>
#include <deque>
#define MAXN 164
#define MAXM 164
using namespace std;
int a[2*MAXN][2*MAXM];
int pre[2*MAXN][2*MAXN];
deque<int>q;
double crt[2*MAXM];
int n, m, r, c;
int verif(int stx,int len,double k)
{
for(int i=1; i<=2*m; i++)
crt[i]=crt[i-1]+pre[stx+len-1][i]-pre[stx-1][i]-(k*len);
if(crt[c]>=0)
return 1;
q.clear();
for(int i=c+1; i<=2*m; i++)
{
while(!q.empty()&&crt[i-c]<=crt[q.back()])
q.pop_back();
q.push_back(i-c);
while(q.size()>1&&i-q.front()+1>m)
q.pop_front();
double scad=crt[q.front()];
if(crt[i]-scad>=0)
return 1;
}
return 0;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&r,&c);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
a[i][j+m]=a[i+n][j]=a[i+n][j+m]=a[i][j];
}
for(int i=1; i<=2*n; i++)
for(int j=1; j<=2*m; j++)
pre[i][j]=pre[i-1][j]+a[i][j];
int rez=0;
for(int i=1; i<= n; i++)
for(int j=r; j<=n; j++)
{
int ls=rez,ld=(1<<30),k;
if(!verif(i,j,ls/1000.0))
continue;
for(int it=1; it<=30&&ls<ld; it++)
{
k=(ls+ld)/2;
if(verif(i,j,k/1000.0))
ls=k;
else
ld=k-1;
}
for(; verif(i,j,ls/1000.0); ++ls);
if(!verif(i,j,ls/1000.0))
--ls;
rez=max(rez,ls);
}
printf("%.3f",rez/1000.0);
return 0;
}