Pagini recente » Cod sursa (job #2403460) | Cod sursa (job #2453313) | Cod sursa (job #2871256) | Cod sursa (job #739835) | Cod sursa (job #186875)
Cod sursa(job #186875)
#include <cstdio>
#include <queue>
using namespace std;
#define MAX_N 310
#define f first
#define s second
#define mp make_pair
int A[MAX_N][MAX_N];
double B[MAX_N][MAX_N], S[MAX_N];
int i,j,k,l,n,m,r,c;
double st,dr, mx;
double max(double a, double b) { return a<b?b:a; }
typedef pair<double, int> di;
struct comp {
bool operator()(di A, di B) {
return A.f > B.f;
}
};
int valid( double 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];
priority_queue<di, vector<di>, comp> Q;
for ( k=c; k<=n; ++k ) {
Q.push( mp(S[k-c], k) );
if ( S[k]-Q.top().f>=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("%d", A[i]+j);
A[i+n][j] = A[i][j+n] = A[i+n][j+n] = A[i][j];
mx = max(mx, 1.*A[i][j]);
}
n *= 2, m *= 2;
st = 0, dr = 2*mx;
while ( st<=dr && dr-st > 0.0001 ) {
double mij = (st+dr)/2;
if ( valid(mij) )
st = mij;
else
dr = mij;
}
fprintf(fopen("balans.out", "w"), "%.3lf\n", st);
return 0;
}