oj.uz

답안 #1100071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100071 2024-10-12T15:55:33 Z andrei_iorgulescu Olympiads (BOI19_olympiads) C++14
0 / 100
 2000 ms 42672 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;
    while (!pq.empty())
    {
        stt++;
        if (stt > 250000)
            assert(false);
        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());
        //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 (!viz[idk])
                cur++;
            viz[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)
                    pq.push(new_nod);
            }
        }
        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 (rau)
                {
                    conf new_nod;
                    new_nod.vv = nod.vv;
                    new_nod.vv[j - 1]++;
                    if (new_nod.vv[j - 1] < n)
                    {
                        pq.push(new_nod);
                        //cout << "ps " << j << endl;
                    }
                }
            }
        }
    }
    return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2055 ms 42672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1176 KB Output is correct
2 Runtime error 1104 ms 5128 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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