Pagini recente » Cod sursa (job #2840176) | Cod sursa (job #2091645) | Cod sursa (job #1086494) | Cod sursa (job #273479) | Cod sursa (job #826852)
Cod sursa(job #826852)
#include <fstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cassert>
using namespace std;
const int MAX_N = 500;
int mat[MAX_N][MAX_N];
long long sumR[MAX_N][MAX_N];
double sumC[MAX_N];
int N, M, R, C;
int dq[MAX_N];
// deque<int> dq;
int sol;
void read_input();
int binary_search();
bool check_answer(double r);
int main() {
read_input();
sol = binary_search();
printf("%d.%03d", sol / 1000, sol % 1000);
return 0;
}
void read_input() {
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
scanf("%d %d %d %d", &N, &M, &R, &C);
if (R == 0) ++R;
if (C == 0) ++C;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
scanf("%d", &mat[i][j]);
mat[i+N][j] = mat[i][j];
mat[i][j+M] = mat[i][j];
mat[i+N][j+M] = mat[i][j];
}
}
for (int i = 1; i <= 2 * N; ++i) {
for (int j = 1; j <= 2 * M; ++j) {
sumR[i][j] = sumR[i-1][j] + mat[i][j];
}
}
}
int binary_search() {
int lo = 0, hi = 100000001, mid = 0;
while (lo + 1 < hi) {
mid = lo + (hi - lo) / 2;
if (check_answer(mid / 1000.0) == true) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
bool check_answer(double r) {
for (int i = 1; i <= N; ++i) {
for (int j = i + R - 1; j <= 2 * N && j - i + 1 <= N; ++j) {
for (int k = 1; k <= 2 * M; ++k) {
sumC[k] = sumC[k-1] + (sumR[j][k] - sumR[i-1][k] - r * (j - i + 1));
//fout << sumC[k] << ' ';
}
//fout << endl;
//if (sumC[C] >= 0) return true;
int front = 1, back = 0;
for (int k = C + 1; k <= 2 * M; ++k) {
dq[++back] = k - C;
while (front < back && sumC[dq[back]] < sumC[dq[back-1]]) dq[back-1] = dq[back], --back;
while(front < back && dq[front] < k - M + 1) ++front;
if (sumC[k] - sumC[dq[front]] >= 0) {
//fout << i << ' ' << j << ' ' << dq[front] << ' ' << k << endl;
return true;
}
}
}
}
return false;
}