Pagini recente » Cod sursa (job #184497) | Cod sursa (job #122693) | Cod sursa (job #1893876) | Cod sursa (job #1743934) | Cod sursa (job #788751)
Cod sursa(job #788751)
#include <fstream>
#include <iomanip>
#include <deque>
#define NM 310
#define Z 1000
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int N,M,i,j,R,C;
int A[NM][NM];
long long SUM[NM][NM];
deque<int> D;
long long ANS=0;
long long V[NM];
int l1,l2;
void Read ()
{
f >> N >> M >> R >> C;
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
{
f >> A[i][j];
A[i][j]*=Z;
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];
f.close();
}
bool Check (long long X)
{
for (l1=1; l1<=N>>1; l1++)
for (l2=l1+R-1; l2<=N; l2++)
{
D.clear();
for (j=1; j<=M; j++)
{
V[j]=V[j-1]+(SUM[l2][j]-SUM[l1-1][j])-X*1LL*(l2-l1+1);
if (j>=C)
{
while (!D.empty() && V[j-C]<=V[D.back()]) D.pop_back();
D.push_back(j-C);
}
while (!D.empty() && j-D.front()>C) D.pop_front();
if (!D.empty() && V[j]-V[D.front()]>=0) return 1;
}
}
return 0;
}
void Solve ()
{
long long P=0,U=1LL*100000*Z,M;
while (P<=U)
{
M=(P+U)>>1;
if (Check(M))
{
ANS=M;
P=M+1;
}
else
U=M-1;
}
}
void Print ()
{
g << fixed << setprecision(3) << (1.0*ANS/Z) << '\n';
g.close();
}
int main ()
{
Read();
Solve();
Print();
return 0;
}