Pagini recente » Cod sursa (job #2312840) | Cod sursa (job #359289) | Cod sursa (job #1521206) | Cod sursa (job #2823906) | Cod sursa (job #803568)
Cod sursa(job #803568)
#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];
long long sumR[MAX_N][MAX_N];
long long sumC[MAX_N];
int N, M, R, C;
int dq[MAX_N];
// deque<int> dq;
void read_input();
int binary_search();
bool check_answer(int r);
int main() {
read_input();
int solution = binary_search();
fout << double(solution) / 1000.0;
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] * 1000;
}
}
}
int binary_search() {
int lo = 0, hi = 100000001, mid;
for (int i = 1; i <= 30; ++i) {
mid = lo + (hi - lo) / 2;
// fout << mid << endl;
if (check_answer(mid) == true) {
lo = mid;
} else {
hi = mid;
}
}
return mid;
}
bool check_answer(int 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;
}