Cod sursa(job #1747256)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 24 august 2016 17:34:01
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <iostream>
#include <cstdio>
using namespace std;
const int dim = 10005;
const int maxn = 305;
int M[maxn][maxn];
int sp[maxn][maxn];
int n, m;
void calc()
{
    for(int i = 1; i <= n * 2; i++)
        for(int j = 1; j <= m * 2; j++)
            sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + M[i][j];
}

inline int get_sum(int x1, int y1, int x2, int y2)
{
    return sp[x2][y2] - sp[x1 - 1][y2] - sp[x2][y1 - 1] + sp[x1 - 1][y1 - 1];
}

char T[dim];
int poz;

inline void cit(int &nr)
{
    nr = 0;
    while(!isdigit(T[poz]))
    {
        if(++poz == dim)
        {
            fread(T, 1, dim, stdin);
            poz = 0;
        }
    }

    while(isdigit(T[poz]))
    {
        nr = nr * 10 + T[poz] - '0';
        if (++poz == dim)
        {
            fread(T, 1, dim, stdin);
            poz = 0;
        }
    }
}


int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);
    int r, c;
    cit(n);
    cit(m);
    cit(r);
    cit(c);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            cit(M[i][j]);
            M[i][j + m] = M[i][j];
            M[i + n][j] = M[i][j];
            M[i + n][j + m] = M[i][j];
        }
    }
    calc();
    long long mx = 0;
    int l = 0;
    int col = 0;
    int x = 0;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            for(int p = i + r - 1; p <= i + n - 1; ++p)
            {
                for(int q = j + c - 1; q <= j + m - 1; ++q)
                {
                    x = get_sum(i, j, p, q);
                    l = (p - i + 1);
                    col = (q - j + 1);
                    if(mx * l * col < 1000LL * x)
                        mx = 1000LL * x / (l * col);
                }
            }
        }
    }
    printf("%lld.", mx / 1000);
    int p = mx % 1000;
    if(p < 10)
        printf("0");
    if(p < 100)
        printf("0");
    printf("%d\n", p);
    return 0;
}