Pagini recente » Cod sursa (job #2149382) | Cod sursa (job #1630797) | Cod sursa (job #2314746) | Cod sursa (job #2613366) | Cod sursa (job #804147)
Cod sursa(job #804147)
#include <fstream>
#include <iomanip>
#include <cassert>
using namespace std;
const int MAX_N = 500;
ifstream fin("balans.in");
ofstream fout("balans.out");
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;
void read_input();
int binary_search();
bool check_answer(double r);
int main() {
read_input();
fout << fixed << setprecision(3) << double(binary_search()) / 1000.0;
return 0;
}
void read_input() {
fin >> 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) {
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];
}
}
}
int binary_search() {
int lo = 0, hi = 100000001, mid;
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);
if (sumC[C] >= 0) return true;
int front = 1, back = 0;
for (int k = C + 1; k <= 2 * M; ++k) {
while (front <= back && sumC[dq[back]] >= sumC[k-C]) --back;
dq[++back] = k - C;
while(front <= back && k - dq[front] + 1 > M) ++front;
if (sumC[k] - sumC[dq[front]] >= 0)
return true;
}
}
}
return false;
}