Cod sursa(job #386917)

Utilizator Mishu91Andrei Misarca Mishu91 Data 26 ianuarie 2010 12:34:20
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <deque>

using namespace std;

#define val first
#define poz second

const int MAX_N = 305;
const int INF = 0x3f3f3f3f;

ifstream fin ("balans.in");
ofstream fout ("balans.out");

int N, M, R, C, Max, A[MAX_N][MAX_N], S[MAX_N][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] *= 10000;

			Max = max(Max, 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];
}

bool works(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;

	int Sol = -INF;
	for(int i = 1; i <= 2*N; ++i)
		for(int k = i+R-1; k <= min(i+N-1, 2*N); ++k)
		{
			int T[MAX_N];
			deque <pair<int, int> > Q;

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

			for(int j = C; j <= 2*M; ++j)
			{
				while(!Q.empty() && Q.back().val > T[j-C]) Q.pop_back();
				while(!Q.empty() && Q.front().poz < j - M) Q.pop_front();

				Q.push_back(make_pair(T[j-C], j-C));

				if(T[j] - Q.front().val > Sol)
					Sol = T[j] - Q.front().val;
			}
		}	

	return (Sol >= 0);
}

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

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

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

	fout << (i/10000) << "." << (i % 10000)/10 << "\n";
}

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