Pagini recente » Cod sursa (job #975976) | Cod sursa (job #1813633) | Cod sursa (job #2562933) | Cod sursa (job #419775) | Cod sursa (job #1489133)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>
#include <deque>
#define DIM 305
#define infile "balans.in"
#define outfile "balans.out"
using namespace std;
ifstream fin(infile);
ofstream fout(outfile);
int n, m, r, c;
int a[DIM][DIM];
long long partialColumnSum[DIM][DIM], aux[DIM];
deque<int> deq;
bool check(int value) {
for (int upRow = 1; upRow <= n; ++upRow) {
for (int downRow = upRow + r - 1; downRow - upRow + 1 <= n; ++downRow) {
for (int column = 1; column <= 2 * m; ++column) {
aux[column] = aux[column - 1] + partialColumnSum[downRow][column] - partialColumnSum[upRow - 1][column] - value * (downRow - upRow + 1);
}
deq.clear();
for (int column = c; column <= 2 * m; ++column) {
while (!deq.empty() && aux[column - c] <= aux[deq.back()])
deq.pop_back();
deq.push_back(column - c);
if (deq.front() < column - m)
deq.pop_front();
if (aux[column] - aux[deq.front()] >= 0)
return true;
}
}
}
return false;
}
int main() {
fin >> n >> m;
fin >> r >> c;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
fin >> a[i][j];
a[i + n][j] = a[i + n][j + n] = a[i][j + n] = a[i][j] = a[i][j] * 1000;
}
}
for (int i = 1; i <= 2 * n; ++i) {
for (int j = 1; j <= 2 * m; ++j) {
partialColumnSum[i][j] = partialColumnSum[i - 1][j] + a[i][j];
}
}
int left = 0, right = (1 << 30), solution = 0;
while (left <= right) {
int middle = left + (right - left) / 2;
if (check(middle)) {
solution = middle;
left = middle + 1;
}
else {
right = middle - 1;
}
}
fout << setprecision(3) << fixed << solution / 1000.0;
return 0;
}
//Trust me, I'm the Doctor!