Cod sursa(job #2032)

Utilizator MariusMarius Stroe Marius Data 15 decembrie 2006 18:25:05
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 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 MAX_BUF 160000
#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;

char buffer[MAX_BUF];


inline char* getnum(char *p, char *lim, int & V)
{
	for (; p < lim && *p < '0'; ++p) 
		;
	for (V = 0; p < lim && *p >= '0'; ++p)
		V = V * 10 + (*p) - '0';

	return p;
}

void read_data(void)
{
	freopen(iname, "r", stdin);
	int i;
	int j;
	int len;

	len = fread(buffer, sizeof(char), MAX_BUF, stdin);
	char *p = buffer;
	char *lim = buffer + len;

	p = getnum(p, lim, N);
	p = getnum(p, lim, M);
	p = getnum(p, lim, R);
	p = getnum(p, lim, C);
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j) {
			p = getnum(p, lim, 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 * N - 1;
	M = 2 * M - 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;
	int step;
	for (step = 1; step <= MargSup; step <<= 1) ;
	for (k = 0; step > 0; step >>= 1)
		if (k + step <= MargSup && determina_balans(k + step))
			k += step;
	print(k);

	return 0;
}