Submission #1224227

#TimeUsernameProblemLanguageResultExecution timeMemory
122422712345678Olympiads (BOI19_olympiads)C++20
44 / 100
772 ms1640 KiB
#include <bits/stdc++.h> using namespace std; const int nx=505; int n, k, c, used[nx], dp[nx][nx], tmp[6]; struct students { int s, idx, a[6]; bool operator< (const students &o) const {return s<o.s;} } s[nx]; students sub[6][nx]; vector<students> req; multiset<int> ms; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>k>>c; dp[0][0]=1; for (int i=1; i<=n+1; i++) for (int j=0; j<=i; j++) dp[i][j]=dp[i-1][j]+(j?dp[i-1][j-1]:0); //cout<<"dp "<<i<<' '<<j<<' '<<dp[i][j]<<'\n'; for (int i=0; i<n; i++) for (int j=0; j<k; j++) cin>>s[i].a[j]; for (int i=0; i<k; i++) for (int j=0; j<n; j++) sub[i][j]=s[j], sub[i][j].s=s[j].a[i], sub[i][j].idx=j; for (int i=0; i<k; i++) sort(sub[i], sub[i]+n), reverse(sub[i], sub[i]+n); for (int i=0; i<n; i++) { for (int j=0; j<k; j++) { if (!used[sub[j][i].idx]&&dp[req.size()+1][k]<10000000) { used[sub[j][i].idx]=1; req.push_back(sub[j][i]); } } } int sz=req.size(); for (int A=0; A<sz; A++) { if (k==1) { int sm=0; for (int i=0; i<k; i++) sm+=req[A].a[i]; ms.insert(sm); if (ms.size()>c) ms.erase(ms.begin()); continue; } for (int B=A+1; B<sz; B++) { if (k==2) { int sm=0; for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i]}); ms.insert(sm); if (ms.size()>c) ms.erase(ms.begin()); continue; } for (int C=B+1; C<sz; C++) { if (k==3) { int sm=0; for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i]}); ms.insert(sm); if (ms.size()>c) ms.erase(ms.begin()); continue; } for (int D=C+1; D<sz; D++) { if (k==4) { int sm=0; for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i], req[D].a[i]}); ms.insert(sm); if (ms.size()>c) ms.erase(ms.begin()); continue; } for (int E=D+1; E<sz; E++) { if (k==5) { int sm=0; for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i], req[D].a[i], req[E].a[i]}); ms.insert(sm); if (ms.size()>c) ms.erase(ms.begin()); continue; } for (int F=E+1; F<sz; F++) { int sm=0; for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i], req[D].a[i], req[E].a[i], req[F].a[i]}); ms.insert(sm); if (ms.size()>c) ms.erase(ms.begin()); continue; } } } } } } auto itr=prev(ms.end()); while (--c) --itr; cout<<*itr; } /* 5 3 4 7 0 4 3 0 8 1 1 3 5 1 3 4 2 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...