Pagini recente » Cod sursa (job #264771) | Cod sursa (job #637413) | Cod sursa (job #2383543) | Cod sursa (job #1202182) | Cod sursa (job #1413968)
#include <fstream>
#include <deque>
#define MAXN 160
#define MAXVAL 100005
#define INF 2000000000000000000
using namespace std;
int n, m, r, c, a[2 * MAXN][2 * MAXN], i1, i2;
long long Sp[2 * MAXN][2 * MAXN];
inline long long val(int j){
return Sp[i2][j] - Sp[i1 - 1][j];
}
bool works(int x){
int i, j;
long long maxS = -INF, y;
deque<int> dq;
for(i = 1; i <= 2 * n; i++)
for(j = 1; j <= 2 * m; j++)
Sp[i][j] = Sp[i - 1][j] + Sp[i][j - 1] - Sp[i - 1][j - 1] + a[i][j] - x;
/*printf("%d:\n", x);
for(i = 1; i <= 2 * n; i++, printf("\n"))
for(j = 1; j <= 2 * m; j++)
printf("%8lld ", Sp[i][j]); */
for(i1 = 1; i1 <= n && maxS < 0; i1++)
for(i2 = i1 + r - 1; maxS < 0 && i2 - i1 + 1 <= n; i2++){
dq.clear();
for(j = c; j <= 2 * m; j++){
y = val(j - c);
while(!dq.empty() && y < val(dq.back())) dq.pop_back();
dq.push_back(j - c);
while(j - dq.front() > m) dq.pop_front();
y = val(j) - val(dq.front());
if(y > maxS) maxS = y;
}
}
//printf("%lld\n\n", maxS);
return maxS >= 0;
}
int main(){
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
int i, j;
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][j] *= 1000;
}
for(i = n + 1; i <= 2 * n; i++)
for(j = 1; j <= m; j++)
a[i][j] = a[i - n][j];
for(i = 1; i <= n; i++)
for(j = m + 1; j <= 2 * m; j++)
a[i][j] = a[i][j - m];
for(i = n + 1; i <= 2 * n; i++)
for(j = m + 1; j <= 2 * m; j++)
a[i][j] = a[i - n][j - m];
int l = 0, r = MAXVAL * 1000, mid;
while(l < r){
mid = (l + r) >> 1;
if(works(mid)) l = mid + 1;
else r = mid - 1;
}
while(!works(l)) l--;
printf("%d.%03d\n", l / 1000, l % 1000);
return 0;
}