Cod sursa(job #2711268)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 23 februarie 2021 20:56:58
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda simulare_nr1 Marime 1.95 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("elimin.in");
ofstream fout("elimin.out");
int n, m, a[100][100], r, c, s[100][100], ans = INT_MIN;
int suma;
bool marked[100][100];
void rezolvare(int nrl, int nrcl, int linie, int coloana) {
    if (nrl < r) {
        for (int i = linie; i <= n; ++i) {
            if (i == 0)
                continue;
            for (int j = 1; j <= m; ++j) {
                if (!marked[i][j]) {
                    suma -= a[i][j];
                    marked[i][j] = true;
                }
            }
            rezolvare(nrl + 1, nrcl, i + 1, coloana);
            for (int j = 1; j <= m; ++j) {
                if (!marked[i][j]) {
                    suma += a[i][j];
                    marked[i][j] = false;
                }
            }
        }
    }
    else if (nrl == r) {
        if (nrcl < c) {
            for (int j = coloana; j <= m; ++j) {
                for (int i = 1; i <= n; ++i) {
                    if (!marked[i][j]) {
                        suma -= a[i][j];
                        marked[i][j] = true;
                    }
                }
                rezolvare(nrl, nrcl + 1, linie, j + 1);
                for (int i = 1; i <= n; ++i) {
                    if (!marked[i][j]) {
                        suma += a[i][j];
                        marked[i][j] = false;
                    }
                }
            }
        }
        else if (suma > ans) {
            ans = suma;
            return;
        }
    }

}

int main()
{
    fin >> n >> m >> r >> c;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }

    suma = s[n][m];
    rezolvare(0, 0, 0, 0);

    fout << ans;
    return 0;
}