Cod sursa(job #1593957)

Utilizator ZenusTudor Costin Razvan Zenus Data 9 februarie 2016 01:02:08
Problema Balans Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 309;

int n , m , r , c , i , j , k , p , ok;
int a[nmax][nmax];
long long sc[nmax][nmax] , s[nmax];
double result , low , high , f[nmax] , v , mn , g;

int main()
{
freopen("balans.in" , "r" , stdin);
freopen("balans.out" , "w" , stdout);

scanf("%d" , &n);
scanf("%d" , &m);
scanf("%d" , &r);
scanf("%d" , &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 + m] = a[i + n][j + m] = a[i][j];
}

n = 2 * n , m = 2 * m;

for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= m ; ++j)
sc[i][j] = sc[i - 1][j] + a[i][j];

result = 0;
for (i = 1 ; i <= n ; ++i)
for (j = i + r - 1 ; j <= n ; ++j)
{
    for (k = 1 ; k <= m ; ++k)
    s[k] = sc[j][k] - sc[i - 1][k];

    for (k = 2 ; k <= m ; ++k)
    s[k] += s[k - 1];

    double low = 0 , high = 100000;

    for (p = 1 ; p <= 100 ; ++p)
    {
        v = (low + high) / 2;
        ok = false;

        for (k = 1 ; k <= m ; ++k)
        f[k] = s[k] - v * k * (j - i + 1);

        mn = 0;
        for (k = c ; k <= m ; ++k)
        {
            if (f[k] >= mn) ok = true;
            mn = min(mn , f[k - c + 1]);
        }

        if (ok) g = v , low = v;
        else high = v;
    }

    result = max(result , g);
}

printf("%.3lf\n" , result);

return 0;
}