Pagini recente » Cod sursa (job #204788) | Cod sursa (job #573205) | Cod sursa (job #1873376) | Cod sursa (job #2036038) | Cod sursa (job #676960)
Cod sursa(job #676960)
#include <cstdio>
#include <algorithm>
#define NMax 305
#define Infinity 100000000
using namespace std;
int N, M, R, C, D[NMax], A[NMax][NMax];
long long SumC[NMax][NMax];
double Solution;
inline long long MSS (long long Sum[])
{
long long SMax=Sum[C];
int F=1, B=0;
D[1]=0;
for (int i=C; i<=M+M; ++i)
{
while (F<=B and D[F]<i-M)
{
++F;
}
while (F<=B and Sum[i-C]<=Sum[D[B]])
{
--B;
}
D[++B]=i-C;
SMax=max (SMax, Sum[i]-Sum[D[F]]);
}
return SMax;
}
inline void BuildSum (long long Sum[], int L1, int L2, long long S)
{
Sum[0]=0;
for (int i=1; i<=M+M; ++i)
{
Sum[i]=Sum[i-1]+SumC[L2][i]-SumC[L1-1][i]-(L2-L1+1)*S;
}
}
inline bool FindMSM (long long S)
{
long long Sum[NMax];
for (int L1=1; L1<=N; ++L1)
{
for (int L2=L1+R-1; L2<=L1+N-1; ++L2)
{
BuildSum (Sum, L1, L2, S);
if (MSS (Sum)>=0)
{
return true;
}
}
}
return false;
}
void Solve ()
{
long long L=0, R=Infinity;
while (L<=R)
{
long long Mid=(L+R)/2;
if (FindMSM (Mid))
{
Solution=Mid;
L=Mid+1;
}
else
{
R=Mid-1;
}
}
}
void Read ()
{
freopen ("balans.in", "r", stdin);
scanf ("%d %d %d %d", &N, &M, &R, &C);
if (R==0) R=1;
if (C==0) C=1;
for (int i=1; i<=N; ++i)
{
for (int j=1; j<=M; ++j)
{
scanf ("%d", &A[i][j]);
A[i][j]*=1000;
A[i+N][j]=A[i][j+M]=A[i+N][j+M]=A[i][j];
}
}
for (int i=1; i<=N+N; ++i)
{
for (int j=1; j<=M+M; ++j)
{
SumC[i][j]=SumC[i-1][j]+A[i][j];
}
}
}
void Print ()
{
freopen ("balans.out", "w", stdout);
printf ("%.3lf\n", (Solution*1.0)/1000);
}
int main()
{
Read ();
Solve ();
Print ();
return 0;
}