Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #788897)
Cod sursa(job #788897)
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MaxN = 305;
int N, M, R, C, A[MaxN][MaxN], AMax, AMin, Solution;
LL SumC[MaxN][MaxN], Sum[MaxN];
int D[MaxN];
inline bool MSS() {
LL MaxS = Sum[C];
int F=1, B=0; D[1] = 0;
for (int i = C; i <= M+M; ++i) {
for (; F <= B && D[F] < i-M; ++F);
for (; F <= B && Sum[i-C+1] <= Sum[D[B]]; --B);
D[++B] = i-C;
MaxS = max(MaxS, Sum[i]-Sum[D[F]]);
if (D[F] > M)
break;
}
return MaxS >= 0;
}
inline void BuildSum(const int L1, const int L2, const 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]-1LL*(L2-L1+1)*S;
}
inline bool FindMSM(const int S) {
for (int L1 = 1; L1 <= N; ++L1) {
for (int L2 = L1+R-1; L2 <= L1+N-1; ++L2) {
BuildSum(L1, L2, S);
if (MSS())
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(AMax, A[i][j]);
AMin = min(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", (1.0*Solution)/1000.0);
}
int main() {
Read();
Solve();
Print();
return 0;
}