Cod sursa(job #186881)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 28 aprilie 2008 23:06:18
Problema Balans Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <queue>
using namespace std;
#define MAX_N 310
#define f first
#define s second
#define mp make_pair

long long A[MAX_N][MAX_N];
long long B[MAX_N][MAX_N], S[MAX_N];
int i,j,k,l,n,m,r,c;
long long st,dr, mx;

long long max(long long a, long long b) { return a<b?b:a; }
typedef pair<long long, int> di;


int valid( long long x ) {
	for ( i=1; i<=n; ++i ) 
		for ( j=1; j<=m; ++j ) 
			B[i][j] = B[i-1][j] + A[i][j] - x;
	for ( i=1; i<=n; ++i )
		for ( j=i+r-1; j<=n; ++j ) {
			S[0] = 0;
			for ( k=1; k<=m; ++k ) 
				S[k] = S[k-1] + B[j][k] - B[i-1][k];
			long long mn = 0x3f3f3f3f * 0x3f3f3f3f;
			for ( k=c; k<=n; ++k ) {
				mn = min(mn, S[k-c]);
				if ( S[k]-mn>=0 ) return 1;
			}
		}
	return 0;
}

int main() {
	freopen("balans.in", "r", stdin);
	scanf("%d %d %d %d", &n, &m, &r, &c);
	for ( i=1; i<=n; ++i )
		for ( j=1; j<=m; ++j ) {
			scanf("%lld", A[i]+j);
			A[i][j] *= 1000;
			A[i+n][j] = A[i][j+n] = A[i+n][j+n] = A[i][j];
			mx = max(mx, A[i][j]);
		}
	n *= 2, m *= 2;

	for ( dr=1; dr<=mx; dr<<=1 );
	for ( st=0; dr; dr>>=1 )
		if ( st+dr<=mx && valid(st+dr) )
			st += dr;
	long long p = (long long)st;
	fprintf(fopen("balans.out", "w"), "%lld.%03lld\n", p/1000, p%1000);
	return 0;
}