Cod sursa(job #804007)

Utilizator toranagahVlad Badelita toranagah Data 28 octombrie 2012 18:07:58
Problema Balans Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <cstdio>
#include <iomanip>
using namespace std;
const int MAX_N = 500;

ifstream fin("balans.in");
// ofstream fout("test.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();
	freopen("balans.out", "w", stdout);
	// fout << fixed << setprecision(3) << double(binary_search()) / 1000.0;
	printf("%.3f", double(binary_search() / 10000.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];
		}
	}
}

int binary_search() {
	int lo = 0, hi = 100000001, mid;
	while (lo + 1 < hi) {
		mid = lo + (hi - lo) / 2;
		// fout << mid << endl;
		if (check_answer(mid / 10000.0) == true) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	// while (!check_answer(lo / 1000.0)) ++mid;
	// if (!check_answer(lo / 1000.0)) --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) {
					// fout << i << ' ' << j << ' ';
					// fout << dq[front] << ' ' << k << endl;
					return true;
				}
			}
		}
	}
	return false;
}