Cod sursa(job #2923413)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 13 septembrie 2022 14:36:29
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>
#define MAXN 90

using namespace std;

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

int mat[MAXN][MAXN], sumRows[MAXN], sumCols[MAXN];

int main() {
    int n, m, r, c, maxi = INT_MIN;
    fin >> n >> m >> r >> c;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            fin >> mat[i][j];
            sumCols[i] += mat[i][j];
            sumRows[j] += mat[i][j];
        }

    // removing rows
    for (int row = 0; row < r; row++) {
        // finding best candidate
        int mini = INT_MAX, index = -1;
        for (int j = 0; j < m; j++)
            if (sumRows[j] > 0 && sumRows[j] < mini) {
                mini = sumRows[j];
                index = j;
            }
        sumRows[index] = -1;

        // updating
        for (int j = 0; j < n; j++)
            sumCols[j] -= mat[j][index];
    }

    // removing columns
    for (int column = 0; column < c; column++) {
        // finding best candidate
        int mini = INT_MAX, index = -1;
        for (int i = 0; i < n; i++)
            if (sumCols[i] > 0 && sumCols[i] < mini) {
                mini = sumCols[i];
                index = i;
            }
        sumCols[index] = -1;

        // updating
        for (int i = 0; i < m; i++)
            sumRows[i] -= mat[index][i];
    }

    for (int i = 0; i < n; i++)
        if (sumCols[i] > 0)
            maxi += sumCols[i];

    // doing the same inverse
    memset(sumCols, 0, n * sizeof(int));
    memset(sumRows, 0, m * sizeof(int));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            sumCols[i] += mat[i][j];
            sumRows[j] += mat[i][j];
        }

    // removing columns
    for (int column = 0; column < c; column++) {
        // finding best candidate
        int mini = INT_MAX, index = -1;
        for (int i = 0; i < n; i++)
            if (sumCols[i] > 0 && sumCols[i] < mini) {
                mini = sumCols[i];
                index = i;
            }
        sumCols[index] = -1;

        // updating
        for (int i = 0; i < m; i++)
            sumRows[i] -= mat[index][i];
    }

    // removing rows
    for (int row = 0; row < r; row++) {
        // finding best candidate
        int mini = INT_MAX, index = -1;
        for (int j = 0; j < m; j++)
            if (sumRows[j] > 0 && sumRows[j] < mini) {
                mini = sumRows[j];
                index = j;
            }
        sumRows[index] = -1;

        // updating
        for (int j = 0; j < n; j++)
            sumCols[j] -= mat[j][index];
    }

    int sum = 0;
    for (int i = 0; i < n; i++)
        if (sumCols[i] > 0)
            sum += sumCols[i];

    // result
    if (sum > maxi)
        maxi = sum;
    fout << maxi;

    return 0;
}