Cod sursa(job #2638786)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 29 iulie 2020 20:11:34
Problema Balans Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, M, R, C;

int a[301][301];
long long sp[301][301];

double sol = -1;

int main()
{
    f >> N >> M >> R >> C;

    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= M; ++ j ){
            f >> a[ i ][ j ];
            a[ i + N ][ j ] = a[ i ][ j ];
            a[ i ][ j + M ] = a[ i ][ j ];
            a[ i + N ][ j + M ] = a[ i ][ j ];
        }
    }
    N *= 2, M *= 2;

    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= M; ++ j ) {
            sp[ i ][ j ] = (sp[ i - 1 ][ j ] + sp[ i ][ j - 1 ] - sp[ i - 1 ][ j - 1 ] + a[ i ][ j ]);
        }
    }

    for (int r = R; r <= N / 2; ++ r ) {
        for (int c = C; c <= M / 2; ++ c ) {

            int Max = 0;

            for (int i = N / 2 + 1; i <= N; ++ i ) {
                for (int j = M / 2 + 1; j <= M; ++ j ) {
                    int sum = sp[ i ][ j ] - sp[ i - r ][ j ] - sp[ i ][ j - c ] + sp[ i - r ][ j - c ];

                    if (sum > Max) {
                        Max = sum;
                    }
                }
            }

            double rez = (double)Max / (r * c);

            if (rez > sol) {
                sol = rez;
            }
        }
    }

    g << setprecision(3) << fixed <<  sol << '\n';

    return 0;
}