Submission #1100092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100092		andrei_iorgulescu	Olympiads (BOI19_olympiads)	C++14	13 / 100	2035 ms	113800 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);
    }
};

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;
    int cur = 0;
    map<vector<int>, bool> viz, vizz;
    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;*/
        bool mistaken = false;
        for (int j = 0; j + 1 < k; j++)
            if (idk[j] == idk[j + 1])
                mistaken = true;
        if (!mistaken)
        {
            if (!vizz[idk])
                cur++;
            vizz[idk] = true;
            if (cur == c)
            {
                cout << value(idk);
                return 0;
            }
            for (int j = 1; j <= k; j++)
            {
                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 j = 0; j < k; j++)
                        new_idk.push_back(ind[j + 1][new_nod.vv[j]]);
                    sort(new_idk.begin(), new_idk.end());*/
                    if (!viz[new_nod.vv])
                        pq.push(new_nod);
                    viz[new_nod.vv] = true;
                }
            }
        }
        else
        {
            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 (rau)
                {
                    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 'int main()':
olympiads.cpp:86:9: warning: unused variable 'stt' [-Wunused-variable]
   86 |     int stt = 0;
      |         ^~~
olympiads.cpp:87:9: warning: unused variable 'vlm' [-Wunused-variable]
   87 |     int vlm = 1e9;
      |         ^~~

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