Cod sursa(job #2640435)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 6 august 2020 14:11:40
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>

using namespace std;

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

const int NMAX = 3e2 + 5;

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

long long sp[NMAX][NMAX];
long long Num_a, Num_b;

static inline void Read ()
{
    f.tie(nullptr);

    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];
        }

    return;
}

static inline void Build ()
{
    for(int i = 1; i <= (N << 1); ++i)
        for(int j = 1; j <= (M << 1); ++j)
            sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + 1LL * A[i][j];

    return;
}

static inline long long Query (int X1, int Y1, int X2, int Y2)
{
    return sp[X2][Y2] - sp[X2][Y1 - 1] - (sp[X1 - 1][Y2] - sp[X1 - 1][Y1 - 1]);
}

static inline void Solve ()
{
    bool Ok = 0;

    for(int l = L; l <= N; ++l)
        for(int c = C; c <= M; ++c)
        {
            for(int X2 = (N + 1); X2 <= (N << 1); ++X2)
                for(int Y2 = (M + 1); Y2 <= (M << 1); ++Y2)
                {
                    int X1 = X2 - l + 1, Y1 = Y2 - c + 1;

                    long long a = Query(X1, Y1, X2, Y2);
                    long long b = l * c;

                    if(!Ok)
                    {
                        Num_a = a, Num_b = b;

                        Ok = 1;

                        continue;
                    }

                    if(a * Num_b > b * Num_a)
                        Num_a = a, Num_b = b;
                }
        }

    return;
}

static inline void Write ()
{
    long double a = Num_a, b = Num_b;
    long double ans = (long double)(a / b) * (long double)1.0000000000;

    ans = (long double)ans * (long double)1000.0000000000;

    long long q = (long long)ans;

    g << q / (long long)1000 << '.';

    int nr = q % (long long)1000;

    int d_1 = nr / 100;
    int d_2 = (nr / 10) % 10;
    int d_3 = nr % 10;

    g << d_1 << d_2 << d_3 << '\n';

    return;
}

int main()
{
    Read();

    Build();

    Solve();

    Write();

    return 0;
}