Cod sursa(job #3358520)

Utilizator rhyhrrhy1Dinca Matei rhyhrrhy1 Data 17 iunie 2026 12:09:44
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
    int M, N, R, C;
    cin >> M >> N >> R >> C;

    vector<vector<int>> a(M, vector<int>(N));
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            cin >> a[i][j];

    int ans = 0;

    if(N <= M) {
        int keepCols = N - C;
        int keepRows = M - R;

        for(int mask = 0; mask < (1 << N); mask++) {
            if(__builtin_popcount(mask) != keepCols) continue;

            vector<int> rowSum(M, 0);

            for(int i = 0; i < M; i++) {
                for(int j = 0; j < N; j++) {
                    if(mask & (1 << j)) {
                        rowSum[i] += a[i][j];
                    }
                }
            }

            sort(rowSum.begin(), rowSum.end(), greater<int>());

            int sum = 0;
            for(int i = 0; i < keepRows; i++) {
                sum += rowSum[i];
            }

            ans = max(ans, sum);
        }
    }

    else {
        int keepRows = M - R;
        int keepCols = N - C;

        for(int mask = 0; mask < (1 << M); mask++) {
            if(__builtin_popcount(mask) != keepRows) continue;

            vector<int> colSum(N, 0);

            for(int j = 0; j < N; j++) {
                for(int i = 0; i < M; i++) {
                    if(mask & (1 << i)) {
                        colSum[j] += a[i][j];
                    }
                }
            }

            sort(colSum.begin(), colSum.end(), greater<int>());

            int sum = 0;
            for(int j = 0; j < keepCols; j++) {
                sum += colSum[j];
            }

            ans = max(ans, sum);
        }
    }

    cout << ans;
}