oj.uz

답안 #1100077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100077 2024-10-12T16:06:57 Z andrei_iorgulescu Olympiads (BOI19_olympiads) C++14
0 / 100
 450 ms 14852 KB 
#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());
        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

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

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 2140 KB Output is correct
2 Correct 450 ms 14852 KB Output is correct
3 Correct 21 ms 1884 KB Output is correct
4 Correct 24 ms 2140 KB Output is correct
5 Incorrect 18 ms 1368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -