답안 #1100117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100117	2024-10-12T18:59:29 Z	andrei_iorgulescu	Olympiads (BOI19_olympiads)	C++14	컴파일 오류	0 ms	0 KB

olympiads

#include <bits/stdc++.h>

using namespace std;

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

struct cmp
{
    bool operator ()(vector<int> A, vector<int> B) const{
        int s1 = 0, s2 = 0;
        for (int i = 0; i < k; i++)
            s1 += a[ind[i + 1][A[i]]][i + 1], s2 += a[ind[i + 1][B[i]]][i + 1];
        return s1 < s2;
        }
};

int C(int x, int y)
{
    if (y == 0)
        return 1;
    if (x < y)
        return 0;
    long long ww = 1;
    for (int i = x; i > x - y; i--)
        ww *= i;
    for (int i = 1; i <= y; i++)
        ww /= i;
    if (ww >= (int)1e9)
        ww = (int)1e9;
    return ww;
}

int cnt(vector<int> nod)
{
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
        {
            if (i == j)
                continue;
            int cn1 = ind[i + 1][nod[i]], cn2 = ind[j + 1][nod[j]];
            if (a[cn1][j + 1] > a[cn2][j + 1] or (a[cn1][j + 1] == a[cn2][j + 1] and cn1 < cn2))
                return 0;
        }
    }
    set<int> oameni;
    for (int i = 0; i < k; i++)
        oameni.insert(ind[i + 1][nod[i]]);
    int lft = k - (int)oameni.size();
    int cati = 0;
    for (int i = 1; i <= n; i++)
    {
        bool ok = true;
        for (int j = 1; j <= k; j++)
        {
            int cn = ind[j][nod[j - 1]];
            if (a[i][j] > a[cn][j] or (a[i][j] == a[cn][j] and i <= cn))
                ok = false;
        }
        if (ok)
            cati++;
    }
    int ans = C(cati, lft);
    return ans;
}

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)
        {
            if (a[A][i] != a[B][i])
            {return a[A][i] > a[B][i];}
            else{return A < B;}
        });
    }
    /*for (int i = 1; i <= k; i++)
    {
        cout << i << " -> ";
        for (auto it : ind[i])
            cout << it << ' ';
        cout << endl;
    }*/
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    int cate = 0;
    vector<int> si;
    for (int i = 1; i <= k; i++)
        si.push_back(0);
    pq.push(si);
    map<vector<int, bool>> viz;
    while (!pq.empty())
    {
        vector<int> nod = pq.top();
        pq.pop();
        int s = 0;
        for (int i = 0; i < k; i++)
            s += a[ind[i + 1][nod[i]]][i + 1];
        /*for (auto it : nod)
            cout << it << ' ';
        cout << " -> " << cnt(nod) << endl;*/
        cate += cnt(nod);
        if (cate >= c)
        {
            cout << s;
            return 0;
        }
        for (int i = 0; i < k; i++)
        {
            vector<int> nod2 = nod;
            nod2[i]++;
            if (nod2[i] < n and !viz[nod2])
                pq.push(nod2), viz[nod2] = true;
        }
    }
    return 0;
}

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

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:100:25: error: wrong number of template arguments (1, should be at least 2)
  100 |     map<vector<int, bool>> viz;
      |                         ^~
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from olympiads.cpp:1:
/usr/include/c++/10/bits/stl_map.h:100:11: note: provided for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'
  100 |     class map
      |           ^~~
olympiads.cpp:121:37: error: no match for 'operator[]' (operand types are 'int' and 'std::vector<int>')
  121 |             if (nod2[i] < n and !viz[nod2])
      |                                     ^
olympiads.cpp:122:35: error: no match for 'operator[]' (operand types are 'int' and 'std::vector<int>')
  122 |                 pq.push(nod2), viz[nod2] = true;
      |                                   ^