Pagini recente » Cod sursa (job #86404) | Cod sursa (job #1164899) | Cod sursa (job #1057609) | Cod sursa (job #1744483) | Cod sursa (job #1751182)
#include <iostream>
#include <cstdio>
#define MAXN 164
#define MAXM 164
using namespace std;
int a[2*MAXN][2*MAXM];
int pre[2*MAXN][2*MAXN], deck[2*MAXM];;
double crt[2*MAXM];
int n, m, r, c;
void citire()
{
scanf("%d %d %d %d", &n, &m, &r, &c);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
a[i][j+m] = a[i+n][j] = a[i+n][j+m] = a[i][j];
}
for (int i = 1; i <= 2*n; i++)
for (int j = 1; j <= 2*m; j++)
pre[i][j] = pre[i-1][j] + a[i][j];
}
bool check(int i1, int i2, double x) {
for(int i=1; i<=m; ++i) crt[i]=pre[i2][i]-pre[i1-1][i]-x*(i2-i1+1)+crt[i-1];
if(crt[c]>=0) return 1;
int st=0,dr=-1;
for(int i=c+1; i<=m; ++i) {
for(;st<=dr && crt[deck[dr]]>=crt[i-c]; --dr);
deck[++dr]=i-c;
for(;st<dr && i-deck[st]+1>m; ++st);
if(crt[i]-crt[deck[st]]>=0) return 1;
}
return 0;
}
//int check(int stx, int len, double k)
//{
// for (int i = 1; i <= m; i++)
// crt[i] = crt[i-1] + pre[stx+len-1][i] - pre[stx-1][i] - (k*len);
// if (crt[c] >= 0) return 1;
// int st = 0, dr = -1;
// for (int i = c+1; i <= m; i++) {
// while (st <= dr && crt[i-c] <= crt[deck[dr]])
// dr--;
// deck[++dr] = i-c;
// while (st < dr && i-deck[st]+1 > m)
// st++;
// double scad = crt[deck[st]];
// if (crt[i]-scad >= 0) return 1;
// }
// return 0;
//}
void solve()
{
int rez = 0;
for (int i = 1; i <= n; i++)
for (int j = r; j <= n; j++) {
/*double k, lo = 0, hi = 1000000;
while (hi - lo > 0.00008) {
k = (lo + hi) / 2;
if (check(i, j, k))
lo = k;
else
hi = k;
}
if (lo > rez)
rez = lo;*/
int ls=rez, ld=(1<<30), k;
int lop = j;
j = i+j-1;
if(!check(i,j,ls/1000.0)) continue;
for(int it=1; it<=30 && ls<ld; it++) {
k=(ls+ld)/2;
if(check(i,j,k/1000.0)) ls=k;
else ld=k-1;
}
for(;check(i,j,ls/1000.0);++ls);
if(!check(i,j,ls/1000.0)) --ls;
rez=max(rez,ls);
j = lop;
}
printf("%.3lf", rez/1000.0);
}
int main()
{
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
citire();
solve();
return 0;
}