Cod sursa(job #630437)

Utilizator darrenRares Buhai darren Data 5 noiembrie 2011 16:11:39
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstring>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <deque>

using namespace std;

const int SIZE = 302;
const double eps = 0.0001;

int N, M, R, C;
int A[SIZE][SIZE];
double S[SIZE][SIZE];
int Dq[SIZE], beg, end;

inline double getsum(int i1, int j1, int i2, int j2)
{
	return S[i2][j2] - S[i2][j1 - 1] - S[i1 - 1][j2] + S[i1 - 1][j1 - 1];
}
bool canget(double X)
{
	memset(S, 0, sizeof(S));
	for (int i = 1; i <= N * 2; ++i)
		for (int j = 1; j <= M * 2; ++j)
			S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (1.0 * A[i][j] - X);
	
	double resnow = -100000;
	for (int i = 1; i <= N * 2 - R + 1; ++i)
		for (int j = i + R - 1; j <= min(N * 2, i + N - 1); ++j)
		{
			beg = 0, end = 0;
			
			/*for (int k = C; k <= M * 2; ++k)
			{
				while (beg < end && Dq[beg] < k - M)
					++beg;
				while (beg < end &&  getsum(i, 1, j, k - C) < getsum(i, 1, j, Dq[end - 1]))
					--end;
				Dq[end++] = k - C;
				
				resnow = max(resnow, getsum(i, 1, j, k) - getsum(i, 1, j, Dq[beg]));
			}*/
		}
	
	return (resnow > 0);
}

int main()
{
	ifstream fin("balans.in");
	ofstream fout("balans.out");
	
	
	fin >> N >> M >> R >> C;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
			fin >> A[i][j];
		for (int j = M + 1; j <= 2 * M; ++j)
			A[i][j] = A[i][j - M];
	}
	for (int i = N + 1; i <= 2 * N; ++i)
		for (int j = 1; j <= 2 * M; ++j)
			A[i][j] = A[i - N][j];
	
	double left = 0, right = 100000;
	while (right - left > eps)
	{
		double mid = (left + right) / 2;
		
		if (canget(mid)) left = mid;
		else             right = mid;
	}
	
	fout << fixed << setprecision(3) << left;
	
	fin.close();
	fout.close();
}