Pagini recente » Cod sursa (job #256308) | Cod sursa (job #1790572) | Cod sursa (job #2590336) | Cod sursa (job #190498) | Cod sursa (job #788955)
Cod sursa(job #788955)
#include <fstream>
#include <iomanip>
#include <cstdio>
#define NM 310
#define Z 1000
using namespace std;
int N,M,i,j,R,C,MX,ZN;
int A[NM][NM];
long long SUM[NM][NM];
int ANS=0;
long long V[NM];
long long Min[NM];
int l1,l2;
void Read ()
{
freopen("balans.in","r",stdin);
scanf("%d %d %d %d",&N,&M,&R,&C);
ZN=N;
V[0]=Min[0]=0;
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
{
scanf("%d",&A[i][j]);
A[i][j]*=Z;
MX=max(MX,A[i][j]);
A[i+N][j]=A[i][j];
A[i][j+M]=A[i][j];
A[i+N][j+M]=A[i][j];
}
N<<=1;
M<<=1;
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
SUM[i][j]=SUM[i-1][j]+1LL*A[i][j];
}
bool Check (int X)
{
for (l1=1; l1<=ZN; l1++)
for (l2=l1+R-1; l2<=l1+ZN-1; l2++)
{
for (j=1; j<=M; j++)
{
V[j]=1LL*V[j-1]+SUM[l2][j]-SUM[l1-1][j]-1LL*X*(l2-l1+1);
Min[j]=min(Min[j-1],V[j]);
if (j>=C)
if (V[j]-Min[j-C]>=0) return 1;
}
}
return 0;
}
void Solve ()
{
int P=0,U=MX,M;
while (P<=U)
{
M=(P+U)>>1;
if (Check(M))
{
ANS=M;
P=M+1;
}
else
U=M-1;
}
}
void Print ()
{
freopen("balans.out","w",stdout);
printf("%.3lf",(1.0*ANS)/1000.0);
}
int main ()
{
Read();
Solve();
Print();
return 0;
}