Cod sursa(job #2894632)

Utilizator dfettiDaniel Fetti dfetti Data 28 aprilie 2022 00:02:53
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin("elimin.in");
ofstream fout("elimin.out");

const int N = 50, M = 7300;
int n, m, r, c, keep[N + 1];
ll a[N + 1][M + 1], col[M + 1], ans;

void check() {
    for (int i = 1; i <= m; i++)
        col[i] = 0;

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= m; j++)
            col[j] += a[keep[i]][j];
    }

    sort(col + 1, col + m + 1);

    ll s = 0;
    for (int i = m - c + 1; i <= m; i++)
        s += col[i];
    ans = max(ans, s);
}

void bk(int step) {
    if (step == r + 1) {
        check();
        return;
    }
    for (int i = keep[step - 1] + 1; i <= n - (r - step); i++) {
        keep[step] = i;
        bk(step + 1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fin >> n >> m >> r >> c;
    r = n - r;
    c = m - c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (n <= m)
                fin >> a[i][j];
            else
                fin >> a[j][i];
    if (n > m) {
        swap(n, m);
        swap(r, c);
    }

    bk(1);
    fout << ans;

    return 0;
}