Submission #1100083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100083		andrei_iorgulescu	Olympiads (BOI19_olympiads)	C++14	0 / 100	434 ms	14836 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;
}
 
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;
        return s1 < s2;
    }
};
 
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;
    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());
        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)
        {
            cur++;
            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_idk])
                        pq.push(new_nod);
                    viz[new_idk] = true;
                }
            }
        }
        else
        {
            for (int j = 1; j <= k; j++)
            {
                int cn = ind[j][nod.vv[j]];
                bool rau = false;
                for (int jj = 1; jj <= k; jj++)
                {
                    if (jj != j)
                    {
                        int cnn = ind[jj][nod.vv[jj]];
                        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 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_idk])
                            pq.push(new_nod);
                        viz[new_idk] = true;
                    }
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:129:22: warning: variable 'rau' set but not used [-Wunused-but-set-variable]
  129 |                 bool rau = false;
      |                      ^~~
olympiads.cpp:74:9: warning: unused variable 'stt' [-Wunused-variable]
   74 |     int stt = 0;
      |         ^~~

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