제출 #1369672

#제출 시각아이디문제언어결과실행 시간메모리
1369672AksLolCodingOlympiads (BOI19_olympiads)C++17
100 / 100
65 ms17056 KiB
#include<bits/stdc++.h>
using namespace std;
int a[600][7],n,k,c;
map<vector<int>,bool> mp;
priority_queue<pair<int,vector<int>>> q;
vector<int> g[600];
int cal(vector<int> &v){
    int p[7]={0,0,0,0,0,0,0};
    for(auto x:v){
        for(int i=0;i<k;i++){
            p[i]=max(p[i],a[x][i]);
        }
    }
    int s=0;
    for(int i=0;i<k;i++) s+=p[i];
    return s;
}
int main(){
    cin>>n >>k >>c;
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            cin>>a[i][j];
        }
    }
    vector<int> st;
    for(int i=0;i<k;i++){
        vector<int> v;
        for(int j=1;j<=n;j++) v.push_back(j);
        sort(v.begin(),v.end(),[&](int x,int y){
            return a[x][i]>a[y][i];
        });
        for(int j=1;j<=n;j++){
            g[j].push_back(v[0]);
        }
        for(int j=0;j<n-1;j++){
            g[v[j]].push_back(v[j+1]);
        }
        for(int i=0;i<n;i++){
            if(find(st.begin(),st.end(),v[i])!=st.end()) continue;
            st.push_back(v[i]);
            break;
        }
        sort(v.begin(),v.end());
    }
    sort(st.begin(),st.end());
    mp[st]=1;
    q.push({cal(st),st});
    while(!q.empty()){
        auto [val,s]=q.top();
        q.pop();
        cnt++;
        if(cnt==c){
            cout<<val;
            return 0;
        }
        for(int i=0;i<k;i++){
            int tmp=s[i];
            for(auto v:g[s[i]]){
                if(find(s.begin(),s.end(),v)!=s.end()) continue;
                s[i]=v;
                vector<int> cp=s;
                sort(cp.begin(),cp.end());
                if(!mp[cp]){
                    mp[cp]=1;
                    q.push({cal(cp),cp});
                }
            }
            s[i]=tmp;
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…