Cod sursa(job #386950)

Utilizator Mishu91Andrei Misarca Mishu91 Data 26 ianuarie 2010 13:13:03
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;

const int MAX_N = 305;

ifstream fin ("balans.in");

int N, M, R, C, Max, Min, A[MAX_N][MAX_N];
long long S[MAX_N][MAX_N], T[MAX_N];

void citire()
{
	fin >> N >> M >> R >> C;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
		{
			fin >> A[i][j];
			A[i][j] *= 1000;

			Max = max(Max, A[i][j]);
			Min = min(Min, A[i][j]);
		}

	for(int i = 1; i <= N; ++i)
		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];
}

inline bool works(const int &x)
{
	for(int i = 1; i < 2*N; ++i)
		for(int j = 1; j < 2*M; ++j)
			S[i][j] = S[i-1][j] + A[i][j] - x;

	long long Sol = -1;
	for(int i = 0; i < N; ++i)
		for(int k = i+R; k <= i+N; ++k)
		{
			int Q[MAX_N], li = 1, lf = 0;

			for(int j = 1; j < 2*M; ++j)
				T[j] = T[j-1] + S[k][j] - S[i][j];

			for(int j = C; j < 2*M; ++j)
			{
				while(li <= lf && T[Q[lf]] > T[j-C]) --lf;
				while(li <= lf && Q[li] < j - M) ++li;

				Q[++lf] = j-C;

				if(T[j] - T[Q[li]] > Sol)
					Sol = T[j] - T[Q[li]];
			}
		}	

	return (Sol >= 0);
}

void solve()
{
	int lg = 1, i = Min;

	for(; lg <= Max; lg <<= 1);

	for(; lg; lg >>= 1)
		if(i + lg <= Max && works(i + lg))
			i += lg;

	freopen("balans.out","wt",stdout);
	printf("%d.%03d\n",(i/1000), (i%1000));
}

int main()
{
	citire();
	solve();
}