Cod sursa(job #3358521)

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

int a[105][105];
int rowSum[105];
int colSum[105];

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

    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;

            for(int i = 0; i < M; i++) rowSum[i] = 0;

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

            nth_element(rowSum, rowSum + keepRows, rowSum + M, 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;

            for(int j = 0; j < N; j++) colSum[j] = 0;

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

            nth_element(colSum, colSum + keepCols, colSum + N, greater<int>());

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

            ans = max(ans, sum);
        }
    }

    cout << ans;
}