Pagini recente » Cod sursa (job #2845924) | Cod sursa (job #893557) | Cod sursa (job #1358106) | Cod sursa (job #2945569) | Cod sursa (job #2711720)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int NMAX = 303;
int N, M, R, C, a[NMAX][NMAX], dp[NMAX][NMAX], sum[NMAX];
bool check(const int &x) {
for(int i = 1; i <= (N << 1); ++i)
for(int j = 1; j <= (M << 1); ++j)
dp[i][j] = dp[i - 1][j] + (a[i][j] - x);
for(int l1 = 1; l1 <= N; ++l1)
for(int l2 = l1 + R - 1; l2 <= (N << 1) && l2 < l1 + N; ++l2) {
deque<int> Q;
for(int j = 1; j <= (M << 1); ++j) {
sum[j] = sum[j - 1] + (dp[l2][j] - dp[l1 - 1][j]);
if(j >= C) {
while(!Q.empty() && Q.front() <= j - M)
Q.pop_front();
while(!Q.empty() && sum[j - C] <= sum[Q.back()])
Q.pop_back();
Q.push_back(j - C);
if(sum[j] - sum[Q.front()] >= 0)
return true;
}
}
}
return false;
}
int32_t main() {
fin >> N >> M >> R >> C;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j) {
fin >> a[i][j];
a[i][j] *= 1000;
a[i + N][j] = a[i][j + M] = a[i + N][j + M] = a[i][j];
}
int st = 1, dr = 1e8, ans = 0;
while(st <= dr) {
int mid = (st + dr) >> 1;
if(check(mid)) {
ans = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
fout << ans / 1000 << '.';
ans %= 1000;
if(ans < 100)
fout << '0';
if(ans < 10)
fout << '0';
fout << ans << '\n';
}