Cod sursa(job #3138396)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 19 iunie 2023 13:54:41
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, r, c, ans;
vector < vector <int> > a;
vector <int> columns, rows, sol;

void calculateRow()
{
    for(int j = 1; j <= m; j ++)
        columns[j] = 0;

//    for(int i = 1; i <= n; i ++)
//        cout << sol[i - 1] << " ";
//    cout << "\n";

    for(int i = 1; i <= n; i ++)
    {
        if(sol[i - 1])
            for(int j = 1; j <= m; j ++)
                columns[j] += a[i][j];
    }

    sort(columns.begin() + 1, columns.end());

    int sum = 0;
    for(int j = c + 1; j <= m; j ++)
        sum += columns[j];

    ans = max(ans, sum);
}

void calculateColumn()
{
    for(int i = 1; i <= n; i ++)
        rows[i] = 0;

    for(int j = 1; j <= m; j ++)
    {
        if(sol[j - 1])
            for(int i = 1; i <= n; i ++)
                rows[i] += a[i][j];
    }

    sort(rows.begin() + 1, rows.end());

    int sum = 0;
    for(int i = r + 1; i <= n; i ++)
        sum += rows[i];

    ans = max(ans, sum);
}

void solveRow(int k, int cnt)
{
    if(k == n)
    {
        if(cnt == r)
            calculateRow();
        return;
    }

    if(cnt < r)
    {
        sol[k] = 0;
        solveRow(k + 1, cnt + 1);
    }

    sol[k] = 1;
    solveRow(k + 1, cnt);
}

void solveColumn(int k, int cnt)
{
    if(k == m)
    {
        if(cnt == c)
            calculateColumn();
        return;
    }
    if(cnt < c)
    {
        sol[k] = 0;
        solveColumn(k + 1, cnt + 1);
    }

    sol[k] = 1;
    solveColumn(k + 1, cnt);
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);

    cin >> n >> m >> r >> c;
    a.assign(n + 1, vector <int> (m + 1));

    for(int i = 1 ; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> a[i][j];


    if(n <= m)
        sol.resize(n + 1), columns.resize(m + 1), solveRow(0, 0);
    else
        sol.resize(m + 1), rows.resize(n + 1), solveColumn(0, 0);

    cout << ans;
    return 0;
}