Pagini recente » Cod sursa (job #5482) | Cod sursa (job #415757) | Cod sursa (job #1510381) | Cod sursa (job #1804037) | Cod sursa (job #317825)
Cod sursa(job #317825)
#include <stdio.h>
#define MAX_N 310
int n, m, r, c, i, j, k, p, q, ok, sol;
int A[MAX_N][MAX_N], deque[MAX_N];
int st, dr, mid;
long long sum[MAX_N][MAX_N], suma[MAX_N];
void cit() {
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &r, &c);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
scanf("%d", &A[i][j]);
if (A[i][j] * 1000 > dr) dr = A[i][j] * 1000;
}
for (i = 1; i <= 2 * n; i++)
for (j = 1; j <= 2 * m; j++)
if (i > n || j > m) {
int p = i % n; q = j % m;
if (p == 0) p = n;
if (q == 0) q = m;
A[i][j] = A[p][q];
}
for (i = 1; i <= 2 * n; i++)
for (j = 1; j <= 2 * m; j++)
sum[i][j] = sum[i - 1][j] + A[i][j] * 1000;
}
void solve() {
st = 0; dr++; mid = 0;
while (st + 1 < dr) {
mid = (st + dr) / 2;
//imi trebuie submatricea de suma maxima cu dimensiuni >= (R, C)
ok = 0;
for (i = 1; i <= n; i++) {
for (j = i + r - 1; j <= 2 * n; j++) {
if (j - i + 1 > n) break;
for (k = 1; k <= 2 * m; k++)
suma[k] = suma[k - 1] + (sum[j][k] - sum[i - 1][k] - 1LL * (j - i + 1) * mid);
//am fixat doua linii, problema revenind la determinarea subsecventei de suma maxima cu lungime > C si < M
p = 1; q = 0;
for (k = 1; k <= 2 * m; k++) {
if (k - c > 0) { //adaug in deque elementeul K - C
deque[++q] = k - c;
while (suma[deque[q]] < suma[deque[q - 1]] && q > p) {
deque[q - 1] = deque[q];
q--;
}
while (deque[p] < k - m + 1 && p < q) p++;
if (suma[k] - suma[deque[p]] >= 0) {
ok = 1;
break;
}
}
}
if (ok) break;
}
if (ok) break;
}
if (ok) {
if (mid > sol) sol = mid;
st = mid;
}
else dr = mid;
}
printf("%d.%d", sol/1000, sol%1000);
int cop = sol % 1000;
if (!cop) cop = 1;
while (cop * 10 < 1000) {
cop *= 10;
printf("0");
}
printf("\n");
}
int main() {
cit();
solve();
return 0;
}