Pagini recente » Cod sursa (job #3005079) | Cod sursa (job #2666568) | Cod sursa (job #1773991) | Cod sursa (job #1269799) | Cod sursa (job #803387)
Cod sursa(job #803387)
#include <fstream>
#include <deque>
using namespace std;
const int MAX_N = 500;
ifstream fin("balans.in");
ofstream fout("balans.out");
int mat[MAX_N][MAX_N];
int sumR[MAX_N][MAX_N];
double sumC[MAX_N];
int N, M, R, C;
int dq[MAX_N];
// deque<int> dq;
void read_input();
double binary_search();
bool check_answer(double r);
int main() {
read_input();
fout.precision(10);
fout << binary_search();
return 0;
}
void read_input() {
fin >> N >> M >> R >> C;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
fin >> 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];
}
}
}
double binary_search() {
double lo = 0, hi = 1 << 30, mid;
while (lo + 0.0001 < hi) {
mid = lo + (hi - lo) / 2;
if (check_answer(mid) == true) {
lo = mid;
} else {
hi = mid;
}
}
return mid;
}
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);
if (sumC[C] >= 0) return true;
int p = 1, q = 0;
for (int k = C + 1; k <= 2 * M; ++k) {
while (p <= q && sumC[q] >= sumC[k-C]) --q;
dq[++q] = k - C;
while(p <= q && k - dq[p] + 1 > M) ++p;
if (sumC[k] - sumC[dq[p]] >= 0)
return true;
}
}
}
return false;
}