Pagini recente » Cod sursa (job #156276) | Cod sursa (job #2842058) | Cod sursa (job #2556480) | Cod sursa (job #1330622) | Cod sursa (job #2154437)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("balans.in");
ofstream out("balans.out");
typedef long long ll;
const int NMAX = 150;
const int NORM = 1e3;
int n, m, r, c;
ll res;
ll sum[1 + 2 * NMAX];
ll a[1 + 2 * NMAX][1 + 2 * NMAX];
ll sp[1 + 2 * NMAX][1 + 2 * NMAX];
ll maxx;
deque < int > dq;
bool ok(int x) {
fill(sum, sum + 2 * NMAX + 1, 0);
for(int l1 = 1; l1 <= n; l1++) {
for(int l2 = l1 + r - 1; l2 <= n; l2++) {
dq.clear();
for(int j = 1; j <= m; j++)
sum[j] = sum[j - 1] + sp[l2][j] - sp[l1 - 1][j] - (l2 - l1 + 1) * x;
for(int i = c; i <= m; i++) {
while(!dq.empty() && sum[i - c] <= sum[dq.back()])
dq.pop_back();
dq.push_back(i - c);
if(0 <= sum[i] - sum[dq.front()])
return true;
}
}
}
return false;
}
int main()
{
in >> n >> m >> r >> c;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
in >> a[i][j];
a[i][j] *= NORM;
maxx = max(maxx, a[i][j]);
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
n *= 2;
m *= 2;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
sp[i][j] = sp[i - 1][j] + a[i][j];
int from = 0, to = maxx;
while(from <= to) {
ll mid = (from + to) / 2;
if(ok(mid) == true) {
res = mid;
from = mid + 1;
} else
to = mid - 1;
}
out << res / NORM << '.' << res % NORM << '\n';
in.close();
out.close();
return 0;
}