Cod sursa(job #1595071)

Utilizator ZenusTudor Costin Razvan Zenus Data 9 februarie 2016 21:58:56
Problema Balans Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 309;

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

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][j] *= 1000;
    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];

    g = 0;
    for (p = 30 ; p >= 0 ; --p)
    {
        v = g + (1 << p);
        ok = false;

        for (k = 1 ; k <= m ; ++k)
        f[k] = s[k] - 1LL * 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;
    }

    result = max(result , g);
}

printf("%d.%.3d\n" , result / 1000 , result % 1000);

return 0;
}