Pagini recente » Cod sursa (job #1696806) | Cod sursa (job #441031) | Cod sursa (job #3257990) | Cod sursa (job #2057165) | Cod sursa (job #186891)
Cod sursa(job #186891)
#include <cstdio>
#include <queue>
using namespace std;
#define MAX_N 310
#define f first
#define s second
#define mp make_pair
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 st,dr, mx;
long max(long a, long b) { return a<b?b:a; }
int valid( long x ) {
for ( i=1; i<=2*n; ++i )
for ( j=1; j<=2*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<=2*n && j-i+1<=n; ++j ) {
S[0] = 0;
for ( k=1; k<=2*m; ++k )
S[k] = S[k-1] + B[j][k] - B[i-1][k];
long long mn = 0;
if ( c<m )
for ( k=c; k<=2*m; ++k ) {
mn = min(mn, S[k-c]);
if ( S[k]-mn>=0 ) return 1;
}
else
return (S[m]>=0);
}
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("%ld", 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]);
}
if ( r==0 ) r=1;
if ( c==0 ) c=1;
for ( dr=1; dr<=2*mx; dr<<=1 );
for ( st=0; dr; dr>>=1 )
if ( st+dr<=mx && valid(st+dr) )
st += dr;
long p = (long)st;
fprintf(fopen("balans.out", "w"), "%ld.%03ld\n", p/1000, p%1000);
return 0;
}