oj.uz

답안 #760537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760537 2023-06-17T18:22:40 Z Ronin13 Olympiads (BOI19_olympiads) C++14
0 / 100
 103 ms 262144 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 501;
const int kmax = 7;

int a[nmax][kmax];
vector <bool> used(nmax);
int n, k, c;

pair<vector <int>, int> get(){
    int Ans = 0;
    vector <int> ans;
    vector <bool> used1(n + 1, false);
    for(int i = 1; i <= k; i++){
        int mx = -1;
        int mxi;
        for(int j = 1; j <= n; j++){
            if(used[j]) continue;
            if(mx < a[j][i])
                mx = a[j][i], mxi = j;
        }
        Ans += mx;
        if(used1[mxi]){
            for(int j = 1; j <= n; j++){
                if(!used1[j] && !used[j]){
                    mxi = j;
                    break;
                }
            }
        }
        if(used1[mxi]){
            return {{}, 0};
        }
        ans.pb(mxi);
        used1[mxi] = true;
    }

    return {ans, Ans};
}

deque <pair<vector <int>, int> > dq[6000001];


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> c;
    for(int i = 1; i <= n; i++){
        for(int j= 1; j <= k; j++)
            cin >> a[i][j];
    }
    int Ans = get().s;
    dq[Ans].pb({{}, 0});
    while(c--){
        while(dq[Ans].empty()) Ans--;
        vector <int> vv = dq[Ans].back().f;
        int ind = dq[Ans].back().s;
        dq[Ans].pop_back();
        for(int to : vv)
            used[to] = true;
        vector <int> o = get().f;

        for(int i = ind; i < k; i++){
            int x = o[i];
            used[x] = true;
            vector <int> u =  vv;
            u.pb(x);
            dq[get().s].pb({u, i});
            used[x] = false;
        }
        for(int to : vv)
            used[to] = false;
    }
    cout << Ans;
    return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 32.0

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