Cod sursa(job #803522)

Utilizator toranagahVlad Badelita toranagah Data 27 octombrie 2012 19:00:25
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#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 << solution / 1000 << '.' << solution % 1000;
	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;
}