Submission #1100099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100099		andrei_iorgulescu	Olympiads (BOI19_olympiads)	C++14	13 / 100	2051 ms	111584 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

int n, k, c;
int a[2005][10];
vector<int> ind[10];

struct conf
{
    vector<int> vv;
};

int value(vector<int> idx)
{
    int aa = 0;
    for (int i = 1; i <= k; i++)
    {
        int mx = 0;
        for (auto it : idx)
            mx = max(mx, a[it][i]);
        aa += mx;
    }
    return aa;
}

bool real(vector<int> ww)
{
    sort(ww.begin(), ww.end());
    for (int i = 0; i + 1 < k; i++)
        if (ww[i] == ww[i + 1])
            return false;
    return true;
}

struct cmp
{
    bool operator ()(conf A, conf B) const
    {
        vector<int> idkA, idkB;
        for (int j = 0; j < k; j++)
            idkA.push_back(ind[j + 1][A.vv[j]]);
        for (int j = 0; j < k; j++)
            idkB.push_back(ind[j + 1][B.vv[j]]);
        int s1 = value(idkA);
        int s2 = value(idkB);
        //cout << "ufff " << s1 << ' ' << s2 << endl;
        if (s1 != s2)
            return s1 < s2;
        return (int)real(idkA) < (int)real(idkB);
    }
};

map<vector<int>, bool> viz, vizz;
int blabla;
int vls[10];
vector<int> sure;
int cur = 0;

void afis()
{
    vector<int> uh = sure;
    for (int i = 1; i <= blabla; i++)
        uh.push_back(vls[i]);
    sort(uh.begin(), uh.end());
    for (int i = 1; i < uh.size(); i++)
        if (uh[i] == uh[i - 1])
            return;
    if (!vizz[uh])
        cur++;
    vizz[uh] = true;
    if (cur == c)
    {
        cout << value(uh);
        exit(0);
    }
}

void bkt(int pos)
{
    if (pos == blabla + 1)
        afis();
    else
    {
        for (int i = 1; i <= n; i++)
        {
            bool nahh = false;
            for (int j = 1; j < pos; j++)
                if (vls[j] == i)
                    nahh = true;
            for (auto it : sure)
                if (it == i)
                    nahh = true;
            if (nahh)
                continue;
            vls[pos] = i;
            bkt(pos + 1);
        }
    }
}

int main()
{
    cin >> n >> k >> c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            ind[j].push_back(i);
    for (int i = 1; i <= k; i++)
    {
        sort(ind[i].begin(), ind[i].end(), [i](int A, int B)
        {
            return a[A][i] > a[B][i];
        });
    }
    /*for (int i = 1; i <= k; i++)
    {
        cout << "woow " << i << endl;
        for (auto it : ind[i])
            cout << it << ' ';
        cout << endl << endl;
    }*/
    priority_queue<conf, vector<conf>, cmp> pq;
    conf c0;
    c0.vv.resize(k);
    for (int i = 0; i < k; i++)
        c0.vv[i] = 0;
    viz[c0.vv] = true;
    pq.push(c0);
    int stt = 0;
    int vlm = 1e9;
    while (!pq.empty())
    {
        conf nod = pq.top();
        pq.pop();
        /*for (int j = 0; j < k; j++)
          cout << nod.vv[j] << ' ';
        cout << endl;*/
        vector<int> idk;
        for (int j = 0; j < k; j++)
            idk.push_back(ind[j + 1][nod.vv[j]]);
        sort(idk.begin(), idk.end());
        //cout << value(idk) << endl;
        //viz[idk] = true;
        /*if (value(idk) > vlm)
            assert(false);
        vlm = value(idk);
        for (auto it : idk)
          cout << it << ' ';
        cout << endl;
        cout << endl;*/
        vector<int> rp;
        for (int i = 1; i < k; i++)
        {
            for (int j = 0; j < i; j++)
            {
                int cn = ind[j + 1][nod.vv[j]];
                int cnn = ind[i + 1][nod.vv[i]];
                if (cn == cnn)
                    rp.push_back(i);
            }
        }
        set<int> neci;
        for (auto it : idk)
            neci.insert(it);
        sure.clear();
        for (auto it : neci)
            sure.push_back(it);
        int rm = k - neci.size();
        blabla = rm;
        bkt(1);
        for (int j = 1; j <= k; j++)
        {
            //cout << "uuu" << endl;
            /*int cn = ind[j][nod.vv[j - 1]];
            bool rau = false;
            for (int jj = 1; jj <= k; jj++)
            {
                if (jj != j)
                {
                    int cnn = ind[jj][nod.vv[jj - 1]];
                    if (cnn == cn)
                        rau = true;
                }
            }*/
            if (true)
            {
                conf new_nod;
                new_nod.vv = nod.vv;
                new_nod.vv[j - 1]++;
                if (new_nod.vv[j - 1] < n)
                {
                    /*vector<int> new_idk;
                    for (int jj = 0; jj < k; jj++)
                        new_idk.push_back(ind[jj + 1][new_nod.vv[jj]]);
                    sort(new_idk.begin(), new_idk.end());*/
                    if (!viz[new_nod.vv])
                        pq.push(new_nod);
                    viz[new_nod.vv] = true;
                }
            }
        }
    }
    return 0;
}

/*
5 2 10
1 7
2 5
3 10
4 8
2 9
*/

Compilation message (stderr)

olympiads.cpp: In function 'void afis()':
olympiads.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 1; i < uh.size(); i++)
      |                     ~~^~~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:132:9: warning: unused variable 'stt' [-Wunused-variable]
  132 |     int stt = 0;
      |         ^~~
olympiads.cpp:133:9: warning: unused variable 'vlm' [-Wunused-variable]
  133 |     int vlm = 1e9;
      |         ^~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32