Cod sursa(job #3040693)

Utilizator unomMirel Costel unom Data 30 martie 2023 11:52:18
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 kb
/*#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");
int n, m, r, c;
int v[1005][1005];
vector <int> lin;
vector <int> sumcol;
long long s;
long long smax = 0;


void bk(int k)
{
    if(k == n+1 && r == 0)
    {
        for(int i = 0; i<lin.size(); i++)
        {
            v[lin[i]][m+1] = -1;
        }

        for(int j = 1; j<=m; j++)
        {
            s = 0;
            for(int i = 1; i<=n; i++)
            {
                if(v[i][m+1] == 0)
                {
                    s += v[i][j];
                }
            }
            sumcol.push_back(s);
        }

        sort(sumcol.begin(), sumcol.end());

        s = 0;

        for(int i = c; i<sumcol.size(); i++)
        {
            s += sumcol[i];
        }

        smax = max(smax, s);

        for(int i = 0; i<lin.size(); i++)
        {
            v[lin[i]][m+1] = 0;
        }
        sumcol.clear();
        return;

    }
    else if(k == n+1)
    {
        return;
    }
    else
    {
        if(r >= 1)
        {
            r--;
            lin.push_back(k);
            bk(k+1);
            r++;
            lin.pop_back();
            bk(k+1);
        }
        else
        {
            bk(k+1);
        }
    }
}

int main()
{
    f>>n>>m>>r>>c;
    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=m; j++)
        {
            f>>v[i][j];
        }
    }

    bk(1);

    g<<smax;
    return 0;
}*/

#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;
}