Pagini recente » Cod sursa (job #2972391) | Cod sursa (job #2200760) | Cod sursa (job #3257228) | Cod sursa (job #2617795) | Cod sursa (job #2352542)
#include <bits/stdc++.h>
#define MAXN 164
#define MAXM 164
int a[2 * MAXN][2 * MAXM] ;
int pre[2 * MAXN][2 * MAXN] ;
std::deque<int>q ;
double crt[2 * MAXM] ;
int n, m, r, c ;
int verif(int stx, int len, double k) {
int i ;
for (i = 1 ; i <= 2 * m ; ++ i)
crt[i] = crt[i - 1] + pre[stx + len - 1][i] - pre[stx - 1][i] - (k * len) ;
if (crt[c] >= 0)
return 1 ;
q.clear() ;
for (i = c + 1 ; i <= 2 * m ; ++ i) {
while (!q.empty() && crt[i - c] <= crt[q.back()])
q.pop_back() ;
q.push_back(i - c) ;
while (q.size() > 1 && i - q.front() + 1 > m)
q.pop_front() ;
double scad = crt[q.front()] ;
if (crt[i] - scad >= 0)
return 1 ; }
return 0 ; }
int main() {
freopen("balans.in", "r", stdin) ;
freopen("balans.out", "w", stdout) ;
scanf("%d %d %d %d", &n, &m, &r, &c) ;
int i, j, it ;
for (i = 1 ; i <= n ; ++ i)
for (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 (i = 1 ; i <= 2 * n ; ++ i)
for (j = 1 ; j <= 2 * m ; ++ j)
pre[i][j] = pre[i - 1][j] + a[i][j] ;
int rez = 0 ;
for (i = 1 ; i <= n ; ++ i)
for (j = r ; j <= n ; ++ j) {
int ls = rez, ld = (1 << 30), k ;
if (!verif(i, j, ls / 1000.0))
continue ;
for (it = 1 ; it <= 30 && ls < ld ; ++ it) {
k = (ls + ld) / 2 ;
if (verif(i, j, k / 1000.0))
ls = k ;
else
ld = k - 1 ; }
for ( ; verif(i, j, ls / 1000.0) ; ++ ls) ;
if (!verif(i, j, ls / 1000.0))
--ls ;
rez = std::max(rez, ls) ; }
printf("%.3f", rez / 1000.0) ;
return 0 ; }