Pagini recente » Cod sursa (job #1368989) | Cod sursa (job #2347319) | Cod sursa (job #1717754) | Cod sursa (job #2167689) | Cod sursa (job #676902)
Cod sursa(job #676902)
#include <cstdio>
#include <algorithm>
#include <deque>
#define NMax 305
#define AMax 100001
#define Eps 1e-7
using namespace std;
int N, M, R, C, A[NMax][NMax], SumC[NMax][NMax];
double Solution;
inline double MSS (double X[])
{
deque <int> D;
double Sum[NMax], SMax=-AMax;
Sum[0]=0;
for (int i=1; i<C; ++i)
{
Sum[i]=Sum[i-1]+X[i];
}
for (int i=C; i<=M+M; ++i)
{
Sum[i]=Sum[i-1]+X[i];
while (!D.empty () and D.front ()<i-M)
{
D.pop_front ();
}
while (!D.empty () and Sum[i-C]<=Sum[D.back ()])
{
D.pop_back ();
}
D.push_back (i-C);
SMax=max (SMax, Sum[i]-Sum[D.front ()]);
}
return SMax;
}
inline void BuildX (double X[], int L1, int L2, double S)
{
for (int i=1; i<=M+M; ++i)
{
X[i]=(double)SumC[i][L2]-(double)SumC[i][L1-1]-(double)(L2-L1+1)*S;
}
}
inline bool FindMSM (double S)
{
double X[NMax];
for (int L1=1; L1<=N+N; ++L1)
{
for (int L2=L1+R-1; L2<=N+N and L2<=L1+N-1; ++L2)
{
BuildX (X, L1, L2, S);
if (MSS (X)>=-Eps)
{
return true;
}
}
}
return false;
}
void Solve ()
{
double L=0, R=AMax;
while (L+Eps<=R)
{
double Mid=(L+R)/2;
if (FindMSM (Mid))
{
Solution=Mid;
L=Mid+Eps;
}
else
{
R=Mid-Eps;
}
}
}
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+N][j]=A[i][j+M]=A[i+N][j+M]=A[i][j];
}
}
for (int j=1; j<=M+M; ++j)
{
for (int i=1; i<=N+N; ++i)
{
SumC[j][i]=SumC[j][i-1]+A[i][j];
}
}
}
void Print ()
{
freopen ("balans.out", "w", stdout);
Solution=(double)((int)(Solution*1000))/1000.0;
printf ("%.3lf\n", Solution);
}
int main()
{
Read ();
Solve ();
Print ();
return 0;
}