Cod sursa(job #2453008)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 2 septembrie 2019 10:31:17
Problema Balans Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <iomanip>

using namespace std;

ifstream f("balans.in");
ofstream g("balans.out");

const int NMAX =15e1 + 5;

int N, M, L, C, A[2 * NMAX][2 * NMAX];

long long dp[2 * NMAX][2 * NMAX];

long double ans = 0;

static inline long long Sum (int X1, int Y1, int X2, int Y2)
{
    return 1LL * (dp[X2][Y2] - dp[X2][Y1 - 1] - (dp[X1 - 1][Y2] - dp[X1 - 1][Y1 - 1]));
}

int main()
{
    f.tie(NULL);

    f >> N >> M >> L >> C;

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
        {
            f >> A[i][j];

            A[i][j + M] = A[i + N][j] = A[i + N][j + M] = A[i][j];
        }

    for(int i = 1; i <= 2 * N; ++i)
        for(int j = 1; j <= 2 * M; ++j)
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) + 1LL * A[i][j];

    for(int l = L; l <= N; ++l)
        for(int c = C; c <= M; ++c)
        {
            for(int i = 1; i <= N; ++i)
                for(int j = 1; j <= M; ++j)
                {
                    int x1 = i, x2 = i + l - 1;
                    int y1 = j, y2 = j + c - 1;

                    long double Numa = Sum(x1, y1, x2, y2);
                    long double Numb = l * c;

                    ans = max(ans, (long double)(Numa / Numb));
                }
        }

    g << setprecision(3) << fixed;

    g << ans << '\n';

    return 0;
}