Cod sursa(job #2817433)

Utilizator hoprixVlad Opris hoprix Data 13 decembrie 2021 17:50:41
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 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;
}