Cod sursa(job #1489138)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 20 septembrie 2015 17:42:23
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>
#include <deque>

#define DIM 305
#define infile "balans.in"
#define outfile "balans.out"

using namespace std;

ifstream fin(infile);
ofstream fout(outfile);

int n, m, r, c;

int a[DIM][DIM];

long long partialColumnSum[DIM][DIM], aux[DIM];

deque<int> deq;


bool check(int value) {

	for (int upRow = 1; upRow <= n; ++upRow) {

		for (int downRow = upRow + r - 1; downRow - upRow + 1 <= n; ++downRow) {

			for (int column = 1; column <= 2 * m; ++column) {

				aux[column] = aux[column - 1] + partialColumnSum[downRow][column] - partialColumnSum[upRow - 1][column] - 1LL * value * (downRow - upRow + 1);

			}

			deq.clear();

			for (int column = c; column <= 2 * m; ++column) {

				while (!deq.empty() && aux[column - c] <= aux[deq.back()])
					deq.pop_back();

				deq.push_back(column - c);

				if (deq.front() < column - m)
					deq.pop_front();

				if (aux[column] - aux[deq.front()] >= 0)
					return true;

			}

		}

	}

	return false;

}


int main() {

	fin >> n >> m;

	fin >> r >> c;

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j <= m; ++j) {

			fin >> a[i][j];

			a[i + n][j] = a[i + n][j + n] = a[i][j + n] = a[i][j] = a[i][j] * 1000;

		}

	}

	for (int i = 1; i <= 2 * n; ++i) {

		for (int j = 1; j <= 2 * m; ++j) {

			partialColumnSum[i][j] = partialColumnSum[i - 1][j] + a[i][j];

		}

	}


	int left = 0, right = (1 << 30), solution = 0;

	while (left <= right) {

		int middle = left + (right - left) / 2;

		if (check(middle)) {

			solution = middle;

			left = middle + 1;

		}
		else {

			right = middle - 1;

		}

	}

	fout << setprecision(3) << fixed << solution / 1000.0;

	return 0;

}

//Trust me, I'm the Doctor!