Cod sursa(job #3322438)

Utilizator mariusharabariMarius Harabari mariusharabari Data 14 noiembrie 2025 08:26:35
Problema Elimin Scor 40
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

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

    int M, N, R, C;
    fin >> M >> N >> R >> C;
    int R_keep = M - R;
    int C_keep = N - C;

    if (R_keep <= 0 || C_keep <= 0) {
        fout << 0 << endl;
        return 0;
    }

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

    vector<long long> col_sums(N, 0);
    vector<bool> used(M, false);
    long long ans = 0;

    for (int i = 0; i < R_keep; i++) {
        int best_row = -1;
        long long best_score = -1;
        for (int j = 0; j < M; j++) {
            if (used[j]) continue;
            vector<long long> temp = col_sums;
            for (int k = 0; k < N; k++) {
                temp[k] += a[j][k];
            }
            sort(temp.begin(), temp.end(), greater<long long>());
            long long score = 0;
            for (int k = 0; k < C_keep; k++) {
                score += temp[k];
            }
            if (score > best_score) {
                best_score = score;
                best_row = j;
            }
        }
        for (int k = 0; k < N; k++) {
            col_sums[k] += a[best_row][k];
        }
        used[best_row] = true;
        ans = best_score;
    }

    fout << ans << endl;
    return 0;
}