Cod sursa(job #386949)

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

using namespace std;

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

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)
		{
			deque <int> Q;

			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(!Q.empty() && T[Q.back()] > T[j-C]) Q.pop_back();
				while(!Q.empty() && Q.front() < j - M) Q.pop_front();

				Q.push_back(j-C);

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

	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();
}