Cod sursa(job #2758557)

Utilizator trucker4lifeMoraru Radu-Andrei trucker4life Data 10 iunie 2021 23:55:55
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
#define ls1(n) (n & (-n))

using namespace std;

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

int main() {
    int arr[7500][20];
    int row_sum[7500];
    long long ans = 0;

    int n, m, r, c;
    fin >> n >> m >> r >> c;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (m > n)
                fin >> arr[j][i];
            else
                fin >> arr[i][j];

    if (m > n) {
        swap(m, n);
        swap(r, c);
    }

    for (int mask = 0; mask < (1 << m); ++mask) {
        if (__builtin_popcount(mask) == c) {
            for (int i = 1; i <= n; ++i)
                row_sum[i] = 0;
            long long sum = 0;
            for (int i = 1; i <= n; ++i) {
                int msk = mask, pos;
                while(msk) {
                    pos = ls1(msk);
                    msk -= pos;
                    pos = __builtin_ctz(pos);

                    row_sum[i] += arr[i][pos];
                    sum += arr[i][pos];
                }
            }
            sort(row_sum+1, row_sum+n+1);
            for (int i = 1; i <= r; ++i)
                sum -= row_sum[i];

            ans = max(ans, sum);
        }
    }
    fout << ans;
}