Cod sursa(job #177)

Utilizator MariusMarius Stroe Marius Data 6 decembrie 2006 00:03:44
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
using namespace std;

const char iname[] = "balans.in";
const char oname[] = "balans.out";
const int  MaxD = 301;
const int  infinity = 1000000000;

#define MargSup 100000000
#define max(a,b) ((a) > (b) ? (a) : (b))

int N, M, R, C;
int A[MaxD][MaxD];
long long Sum[MaxD], X[MaxD][MaxD];
int deque[MaxD], head, tail;
int Ni, Mi;


void read_data(void)
{
	freopen(iname, "r", stdin);
	int i, j;
	scanf("%d %d %d %d\n", &N, &M, &R, &C);
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j) {
			scanf("%d ", A[i]+j);
			A[i][j+M] = A[i+N][j] = A[i+N][j+M] = A[i][j] *= 1000;
		}
	Ni = N, Mi = M;
	N = 2*Ni-1, M = 2*Mi-1;
}

void print(int m)
{
	freopen(oname, "w", stdout);
	printf("%d.", m / 1000);
	m = m % 1000;
	if (m < 100) printf("0");
	if (m < 10)  printf("0");
	printf("%d", m);
}

int  determina_balans(const int balans)
{
	int i, j, k;
	long long smax = -infinity;

	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			X[i][j] = X[i-1][j] + (long long)(A[i][j] - balans);
	
	for (k = 1; k <= Ni; ++k)
		for (i = k+R-1; i <= N && i < k+Ni; ++i) 
		{
			head = 0;
			tail = 1;
			deque[0] = 0;
			for (j = 1; j <= M; ++j) 
			{
				Sum[j] = Sum[j-1] + (X[i][j] - X[k-1][j]);
				if (j >= C) {
					while (head < tail && deque[head] < j-Mi)
						++head;
					if (smax < Sum[j] - Sum[deque[head]])
						smax = Sum[j] - Sum[deque[head]];
					while (head < tail && Sum[j-C+1] <= Sum[deque[tail-1]])
						--tail;
					deque[tail++] = j-C+1;
				}
			}
		}
	return (smax >= 0);
}		

int  main(void)
{
	read_data();
	
	int  k, step;
	for (step = 1; step <= MargSup; step <<= 1) ;
	for (k = 0; step; step >>= 1)
		if (k + step <= MargSup && determina_balans(k + step))
			k += step;
	print(k);

	return 0;
}