Submission #1187126

#TimeUsernameProblemLanguageResultExecution timeMemory
1187126kl0989eOlympiads (BOI19_olympiads)C++20
100 / 100
31 ms1836 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define vi vector<int> #define vl vector<ll> #define pi pair<int, int> #define pl pair<ll,ll> #define all(x) (x).begin(),(x).end() vector<vi> peop; struct searchable { int sum=0; vi inds; vector<bool> ban; int keep=0; searchable() { inds.resize(peop[0].size()); ban.resize(peop.size(),0); keep=0; } void build(searchable* o, int num) { inds.resize(peop[0].size()); ban=o->ban; keep=num; for (int i=0; i<keep; i++) { inds[i]=o->inds[i]; } ban[o->inds[keep]]=1; build(); } void build() { for (int i=keep; i<peop[0].size(); i++) { int ind=-1; int bst=-1; for (int j=0; j<peop.size(); j++) { if (ban[j]) { continue; } bool ok=1; for (int k=0; k<i; k++) { if (inds[k]==j) { ok=0; break; } } if (!ok) { continue; } if (peop[j][i]>bst) { ind=j; bst=peop[j][i]; } } if (ind==-1) { sum=-1e9; return; } inds[i]=ind; } sum=0; for (int i=0; i<peop[0].size(); i++) { int bst=-1; for (int j=0; j<peop[0].size(); j++) { bst=max(bst,peop[inds[j]][i]); } sum+=bst; } } }; class cmp { public: bool operator() (searchable* a, searchable* b) { return a->sum < b->sum; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,k,c; cin >> n >> k >> c; peop.resize(n,vi(k)); for (int i=0; i<n; i++) { for (int j=0; j<k; j++) { cin >> peop[i][j]; } } searchable* a=new searchable(); a->build(); priority_queue<searchable*,vector<searchable*>,cmp> q; q.push(a); while (1) { searchable* a=q.top(); q.pop(); c--; if (c==0) { cout << a->sum << '\n'; break; } for (int i=a->keep; i<k; i++) { searchable* t=new searchable(); t->build(a,i); q.push(t); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...