Submission #1098541

#TimeUsernameProblemLanguageResultExecution timeMemory
1098541simona1230Olympiads (BOI19_olympiads)C++17
100 / 100
55 ms68508 KiB
#include <bits/stdc++.h> using namespace std; int n,k,c; int a[501][32]; vector<int> v[32]; struct team { int used[501]; int forb[501]; int p[32]; team() { for(int i=1;i<=n;i++) used[i]=forb[i]=0; } bool operator<(const team&t)const { int sum=0; for(int j=1; j<=k; j++) { int curr=v[j][t.p[j]]; sum+=a[curr][j]; } int sum2=0; for(int j=1; j<=k; j++) { int curr=v[j][p[j]]; sum2+=a[curr][j]; } return sum2<sum; } }; priority_queue<team> q; int h; bool cmp(int i1,int i2) { return a[i1][h]>a[i2][h]; } void read() { cin>>n>>k>>c; for(int i=1; i<=n; i++) { for(int j=1; j<=k; j++) { cin>>a[i][j]; v[j].push_back(i); } } for(int i=1; i<=k; i++) h=i,sort(v[i].begin(),v[i].end(),cmp); for(int j=1; j<=k; j++) v[j].push_back(0); for(int i=1; i<=k; i++) for(int j=n; j>=1; j--) v[i][j]=v[i][j-1]; } int comb[501][501]; void prec() { for(int i=0; i<=n; i++) { for(int j=0; j<=i; j++) { if(i==0||j==0)comb[i][j]=1; else comb[i][j]=min(c,comb[i-1][j]+comb[i-1][j-1]); //cout<<i<<" "<<j<<" "<<comb[i][j]<<endl; } } } map<set<int>,int> mp; void solve() { team h; for(int i=1; i<=k; i++) h.p[i]=1,h.used[v[i][1]]=1; q.push(h); while(1) { team t=q.top(); q.pop(); int in=0,lf=0; for(int i=1; i<=n; i++) if(!t.used[i]) lf++; set<int> s; for(int i=1; i<=k; i++) s.insert(v[i][t.p[i]]); mp[s]++; if(mp[s]>1)continue; in=s.size(); c-=comb[lf][k-in]; int sum=0; for(int d=1; d<=k; d++) sum+=a[v[d][t.p[d]]][d]; //cout<<sum<<endl; if(c<=0) { cout<<sum<<endl; return; } team nxt; bool nun=1; for(auto it=s.begin(); it!=s.end(); it++) { team curr=t; int i=*it; curr.forb[i]=1; bool pos=1; for(int d=1; d<=k; d++) { while(curr.p[d]<=n&&curr.forb[v[d][curr.p[d]]])curr.p[d]++; if(curr.p[d]>n)pos=0; else curr.used[v[d][curr.p[d]]]=1; } if(nun&&pos||pos&&nxt<curr) { nxt=curr; nun=0; } if(pos) q.push(curr); } if(!nun); } } void slow() { vector<int> ans; if(k==2) { for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { int sum=0; for(int d=1; d<=k; d++) sum+=max(a[i][d],a[j][d]); ans.push_back(sum); } } } else { for(int i=1; i<=n; i++) { int sum=0; for(int d=1; d<=k; d++) sum+=a[i][d]; ans.push_back(sum); } } sort(ans.begin(),ans.end()); cout<<ans[ans.size()-c]<<endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); read(); if(k<=2)slow(); else { prec(); solve(); } return 0; } /* 9 2 7 1 4 8 3 10 3 3 2 7 5 6 9 3 7 2 4 9 3 */

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:141:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  141 |             if(nun&&pos||pos&&nxt<curr)
      |                ~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...