Submission #1227871

#TimeUsernameProblemLanguageResultExecution timeMemory
122787112345678Olympiads (BOI19_olympiads)C++20
100 / 100
21 ms10596 KiB
#include <bits/stdc++.h> using namespace std; const int nx=505, kx=6; int n, k, c, pw[nx][kx]; struct info { int sm, fixed; vector<int> cur, ban; bool operator < (const info &o) const {return sm<o.sm;} int cal() { int tmp=0; for (int i=0; i<k; i++) { int mx=0; for (int j=0; j<k; j++) mx=max(mx, pw[cur[j]][i]); tmp+=mx; } return tmp; } vector<info> nextinfo() { sm=0; vector<info> nxt; for (int i=fixed; i<k; i++) { info tmp=*this; tmp.fixed=i; vector<int> used(n); for (int j=0; j<tmp.fixed; j++) used[tmp.cur[j]]=1; tmp.ban[tmp.cur[i]]=1; int f=0; for (int j=i; j<k; j++) { pair<int, int> mx={-1, -1}; for (int idx=0; idx<n; idx++) { if (used[idx]||tmp.ban[idx]) continue; mx=max(mx, {pw[idx][j], idx}); } if (mx.second==-1) f=1; else tmp.cur[j]=mx.second, used[mx.second]=1; } if (f) continue; tmp.sm=tmp.cal(); nxt.push_back(tmp); } //cout<<"size "<<nxt.size()<<'\n'; return nxt; } void show() { return; cout<<"cur "; cout<<sm<<" : "; for (int i=0; i<k; i++) cout<<cur[i]<<' '; cout<<'\n'; cout<<"banned : "; for (int i=0; i<n; i++) if (ban[i]) cout<<i<<' '; cout<<'\n'; } }; priority_queue<info> pq; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>k>>c; for (int i=0; i<n; i++) for (int j=0; j<k; j++) cin>>pw[i][j]; vector<int> used(n); info start; start.fixed=0; start.cur.resize(k); start.ban.resize(n); for (int i=0; i<k; i++) { pair<int, int> mx; for (int j=0; j<n; j++) if (!used[j]) mx=max(mx, {pw[j][i], j}); used[mx.second]=1; start.cur[i]=mx.second; } start.sm=start.cal(); pq.push(start); while (--c) { auto cur=pq.top(); pq.pop(); //cout<<"main\n"; cur.show(); auto tmp=cur.nextinfo(); for (auto x:tmp) x.show(), pq.push(x); } cout<<pq.top().sm; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...