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