Cod sursa(job #826852)

Utilizator toranagahVlad Badelita toranagah Data 1 decembrie 2012 12:23:13
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#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;
}