Pagini recente » Cod sursa (job #665753) | Cod sursa (job #1377816) | Cod sursa (job #1212727) | Cod sursa (job #348828) | Cod sursa (job #676967)
Cod sursa(job #676967)
#include <cstdio>
#define NMax 305
#define LL long long
using namespace std;
int N, M, R, C, D[NMax], A[NMax][NMax], AMax, AMin, Solution;
LL SumC[NMax][NMax];
template <class T>
T Max (T a, T b)
{
if (a>b)
{
return a;
}
return b;
}
template <class T>
T Min (T a, T b)
{
if (a<b)
{
return a;
}
return b;
}
inline LL MSS (LL Sum[])
{
LL 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 <LL> (SMax, Sum[i]-Sum[D[F]]);
if (D[F]>M)
{
break;
}
}
return SMax;
}
inline void BuildSum (LL Sum[], int L1, int L2, int S)
{
Sum[0]=0;
for (int i=1; i<=M+M; ++i)
{
Sum[i]=Sum[i-1]+SumC[L2][i]-SumC[L1-1][i]-(LL)(L2-L1+1)*(LL)S;
}
}
inline bool FindMSM (int S)
{
LL 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 ()
{
int L=AMin, R=AMax;
while (L<=R)
{
int 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);
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];
AMax=Max <int> (AMax, A[i][j]);
AMin=Min <int> (AMin, 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;
}