Cod sursa(job #2716393)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 martie 2021 09:44:07
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

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

int a[1024][16], N, M, R, C;
long long ans, sum[1024], best;

void max_self(long long &a, long long b) {
    a = max(a, b);
}

int main() {
    fin >> N >> M >> R >> 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(min(N, M) != M) {
        swap(N, M);
        swap(R, C);
    }
    for(int mask = 0; mask < (1 << M); ++mask)
        if(__builtin_popcount(mask) == C) {
            for(int i = 1; i <= N; ++i)
                sum[i] = 0;
            best = 0;
            for(int j = 1; j <= M; ++j)
                if(!(mask & (1 << (j - 1))))
                    for(int i = 1; i <= N; ++i)
                        sum[i] += a[i][j], best += a[i][j];
            sort(sum + 1, sum + N + 1);
            for(int i = 1; i <= R; ++i)
                best -= sum[i];
            max_self(ans, best);
        }
    fout << ans << '\n';
}