Cod sursa(job #790355)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 20 septembrie 2012 22:47:05
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>
#include<algorithm>

#define maxdim 153

using namespace std;

FILE*f=fopen("balans.in","r");
FILE*g=fopen("balans.out","w");

const long long inf = 1LL<<62;

int n,m,l,c;
int A[maxdim][maxdim];
long long S[maxdim],aux[maxdim],deque[maxdim];

inline long long ssm () {
	long long r = -inf,total = 0;
	
	for ( int i = 1 ; i <= m ; ++i ){
		aux[i] = S[i];
		aux[i] += aux[i-1];
		total += S[i];
	}
	
	long long scad = inf;
	for ( int i = c ; i <= m ; ++i ){
		scad = min(scad,aux[i-c]);
		r = max(r,aux[i]-scad);
	}
	
	int front = 1,back = 0,lung = m-c;
	for ( int i = 1 ; i <= m ; ++i ){
		
		while ( front <= back && aux[ deque[back] ] < aux[i] ){
			deque[back--] = 0;
		}
		deque[++back] = i;
		
		if ( deque[front] < i-lung ){
			++front;
		}
		r = max(r,total-aux[i]+aux[deque[front]]);
	}
	
	return r;
}

inline long long get_max ( int medie ){
	long long r = -inf;
	
	for ( int jos = 1 ; jos <= n ; ++jos ){
		
		int nrl = 1,up = jos;
		for ( int i = 1 ; i <= m ; ++i ){
			S[i] = A[jos][i] - medie;
		}
		
		do{
			if ( nrl >= l ){
				r = max(r,ssm());
			}
			
			++nrl; --up; if ( !up )	up = n;
			for ( int i = 1 ; i <= m ; ++i ){
				S[i] += A[up][i] - medie;
			}
			
		}while ( up != jos );
	}
	
	return r;
}

int main () {
	
	fscanf(f,"%d %d %d %d",&n,&m,&l,&c);
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= m ; ++j ){
			fscanf(f,"%d",&A[i][j]);
			A[i][j] *= 1000;
		}
	}
	
	int p = 0,m,u = 100000000;
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( get_max(m) >= 0 ){
			p = m + 1;
		}
		else{
			//printf("%d\n",u);
			u = m - 1;
		}
	}
	
	fprintf(g,"%.3lf\n",(double)u/1000);
	
	fclose(f);
	fclose(g);
	
	return 0;
}