Pagini recente » Cod sursa (job #1266282) | Cod sursa (job #2163639) | Cod sursa (job #1875384) | Cod sursa (job #3245261) | Cod sursa (job #2154511)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <deque>
using namespace std;
//ifstream in("balans.in");
//ofstream out("balans.out");
typedef long long ll;
const ll NMAX = 160;
int n, m, r, c, p, u;
int a[1 + 2 * NMAX][1 + 2 * NMAX];
ll res;
ll sum[1 + 2 * NMAX];
ll sp[1 + 2 * NMAX][1 + 2 * NMAX];
ll dq[1 + 2 * NMAX];
ll maxx;
bool ok(ll x) {
ll mx;
for(int l1 = 1; l1 <= n; l1++) {
for(int l2 = l1 + r - 1; l2 <= l1 + n - 1; l2++) {
for(int i = 1; i <= 2 * m; i++)
sum[i] = sum[i - 1] + sp[l2][i] - sp[l1 - 1][i] - (l2 - l1 + 1) * x;
mx = sum[c];
dq[1] = 1;
p = 1;
u = 0;
for(int i = c + 1; i <= 2 * m; i++) {
while(p <= u && dq[p] + m - 1 < i)
p++;
while(p <= u && sum[i] - sum[dq[u] - 1] <= sum[i] - sum[i - c])
u--;
dq[++u] = i - c + 1;
mx = max(mx, sum[i] - sum[dq[p] - 1]);
if(m < dq[p])
break;
}
if(0 <= mx)
return true;
}
}
return false;
}
int main()
{
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
//in >> n >> m >> r >> c;
scanf("%d%d%d%d", &n, &m, &r, &c);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
//in >> a[i][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];
maxx = max(maxx, 1LL * a[i][j]);
}
}
for(int i = 1; i <= 2 * n; i++)
for(int j = 1; j <= 2 * m; j++)
sp[i][j] = sp[i - 1][j] + 1LL * a[i][j];
ll from = 0;
ll to = maxx;
while(from <= to) {
ll mid = from + (to - from) / 2;
if(ok(mid) == true) {
res = mid;
from = mid + 1;
} else
to = mid - 1;
}
//out << setprecision(3) << fixed;
//out << res * 1.0 / 1000 << '\n';
printf("%ld.", res / 1000);
printf("%ld", res % 1000);
//in.close();
//out.close();
fclose(stdin);
fclose(stdout);
return 0;
}