Submission #898347

#	Time	Username	Problem	Language	Result	Execution time	Memory
898347		dong_gas	Olympiads (BOI19_olympiads)	C++17	0 / 100	1 ms	604 KiB

olympiads

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

struct state {
    int score;
    vector<int> selected, forced; //선택된 거, 강제된 거
    vector<bool> forbidden; //금지된 거
    bool can;
};

bool operator<(state x, state y) {return x.score<y.score;}

int n,k,c;
int a[505][11];
bool chk[505];

bool is_in(vector<int>& v, int x)  {
    for(int i:v) {
        if(i==x) return true;
    }
    return false;
}

state go(state bef) {
    state ret=bef;
    ret.selected=bef.forced;
    ret.can=true;
    //selected는 각각 순서대로 best점수 유지할 거임
    for(int i=ret.selected.size();i<k;i++) {
        //k개까지 선택할 거임.
        ret.selected.push_back(-1);
        for(int j=0;j<n;j++) {
            //금지된 것 아니고
            //이미 선택된 것 아니고
            if(bef.forbidden[j]) continue;
            if(is_in(ret.selected,j)) continue;

            //아직 선택 안 했거나
            //방금 추가한 학생보다 이벤트 점수 높으면 바꿀 거임.
            if(ret.selected[i]==-1 || a[j][i]>a[ret.selected[i]][i]) {
                ret.selected.pop_back(); ret.selected.push_back(j);
            }
        }        
    }
    vector<int> val(k,0);
    ret.score=0;
    for(int i=0;i<k;i++) {
        for(int j=0;j<k;j++) if(~ret.selected[i]) val[j]=max(val[j],a[ret.selected[i]][j]);
    }
    for(int i=0;i<k;i++) ret.score+=val[i];
    if(ret.selected.back()==-1) ret.can=false;
    return ret;
}

void solve() {
    cin>>n>>k>>c;
    for(int i=0;i<n;i++) for(int j=0;j<k;j++) cin>>a[i][j];
    std::priority_queue<state> pq;
    pq.push({0,{},{},vector<bool>(n,false),1});
    int cnt=0;
    while(c--) {
        state now=pq.top(); pq.pop();      
        if(!c) cout<<now.score;
        for(int i=now.forced.size();i<k;i++) {
            //selected[i]는 선택된 것 중 강제 안 된거..
            //강제 안 된거 하나씩 금지 시키면서 가야 함
            now.forbidden[now.selected[i]]=true;
            state nxt=go(now);
            if (find(nxt.selected.begin(), nxt.selected.end(), -1) == nxt.selected.end())
                pq.push(nxt);
            if(nxt.can) pq.push(nxt);
            now.forbidden[now.selected[i]]=false;
            now.forced.push_back(now.selected[i]);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
}

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:71:9: warning: unused variable 'cnt' [-Wunused-variable]
   71 |     int cnt=0;
      |         ^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32