Cod sursa(job #2042)

Utilizator MariusMarius Stroe Marius Data 15 decembrie 2006 18:47:31
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <cstdio>
using namespace std;

const char iname[] = "balans.in";
const char oname[] = "balans.out";

#define MAX_D	 301
#define infinity 100000000LL
#define MAX_BUF  160000
#define MargSup  100000000LL
#define MAX(a,b) ((a) > (b) ? (a) : (b))

int N, M, R, C;

long long A[MAX_D][MAX_D];

long long Sum[MAX_D], X[MAX_D][MAX_D];

int deque[MAX_D], 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;
	int V;

	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, V);
			A[i][j + M] = A[i + N][j] = A[i + N][j + M] = A[i][j] = (long long)(V * 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);
}

bool determina_balans(const long long 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] + (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;
				}
			}
		}
	if (smax < 0)
		return false;
	return true;
}		

int  main(void)
{
	read_data();
	
	long long k, 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;
}