Pagini recente » Cod sursa (job #2324809) | Cod sursa (job #1552549) | Cod sursa (job #617037) | Cod sursa (job #444908) | Cod sursa (job #256858)
Cod sursa(job #256858)
#include <fstream>
#include <iostream>
using namespace std;
const char iname[] = "balans.in";
const char oname[] = "balans.out";
#define FOR(i, a, b) for (int i = (a); i <= (b); ++ i)
const int MAXN = 300;
int A[MAXN][MAXN], rows, cols, r, c, irows, icols;
typedef long long i64;
void read_in(void) {
ifstream in(iname);
in >> rows >> cols >> r >> c;
FOR (i, 1, rows) FOR (j, 1, cols) {
in >> A[i][j];
A[i][j] *= 1000;
if (i < rows)
A[i + rows][j] = A[i][j];
if (j < cols)
A[i][j + cols] = A[i][j];
if (i < rows && j < cols)
A[i + rows][j + cols] = A[i][j];
}
irows = rows, icols = cols;
rows = 2 * rows - 1, cols = 2 * cols - 1;
in.close();
}
bool work(const int blns) {
int deque[MAXN], *head, *tail;
i64 S[MAXN], T[MAXN] = {0}, ret = -1000000000000LL;
FOR (i, 1, irows) {
FOR (j, 1, cols) S[j] = 0;
FOR (k, i, i + irows - 1) {
FOR (j, 1, cols) S[j] += (i64)(A[k][j] - blns);
if (k - i + 1 >= r) {
head = tail = deque;
*head = 0;
FOR (j, 1, cols) {
T[j] = T[j - 1] + S[j];
if (j >= c) {
while (head <= tail && *head < j - icols)
head ++;
if (ret < T[j] - T[*head])
ret = T[j] - T[*head];
while (head <= tail && T[j - c + 1] <= T[*tail])
tail --;
tail ++, *tail = j - c + 1;
}
}
}
}
}
return ret >= 0;
}
int main(void)
{
read_in();
const int upper_limit = 100000000; // 1e8
int i, delta = 1 << 26;
for (i = 0; delta; delta /= 2)
if ((i + delta <= upper_limit) && work(i + delta))
i += delta;
ofstream out(oname);
out << i / 1000 << ".";
i %= 1000;
out << i / 100 << (i % 100) / 10 << i % 10;
out.close();
return 0;
}