Cod sursa(job #2923861)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 20 septembrie 2022 09:10:37
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int max_size1 = 1e2 + 1, max_size2 = 9e3 + 1;

int a[max_size1][max_size2], l[max_size1], cl[max_size2], m, n, r, c;

long long rez;

void check ()
{
    for (int i = 1; i <= m; i++)
    {
        cl[i] = 0;
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cl[j] += a[l[i]][j];
        }
    }
    sort(cl + 1, cl + m + 1);
    long long s = 0;
    for (int i = m - c + 1; i <= m; i++)
    {
        s += cl[i];
    }
    rez = max(rez, s);
}

void bkt (int k)
{
    for (int i = l[k - 1] + 1; i <= n - (r - k); i++)
    {
        l[k] = i;
        if (k < r)
        {
            bkt(k + 1);
        }
        else
        {
            check();
        }
    }
}

int main ()
{
    in >> n >> m >> r >> c;
    r = n - r;
    c = m - c;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (n <= m)
            {
                in >> a[i][j];
            }
            else
            {
                in >> a[j][i];
            }
        }
    }
    if (n > m)
    {
        swap(n, m);
        swap(r, c);
    }
    bkt(1);
    out << rez;
    in.close();
    out.close();
    return 0;
}