Submission #1098521

#TimeUsernameProblemLanguageResultExecution timeMemory
1098521simona1230Olympiads (BOI19_olympiads)C++17
44 / 100
93 ms41968 KiB
#include <bits/stdc++.h> using namespace std; int n,k,c; int a[501][32]; vector<int> v[32]; int p[32][10048]; int used[501][10048]; int forb[501][10048]; struct team { int id; team() {} team(int i) { id=i; } bool operator<(const team&t)const { int sum=0; for(int j=1; j<=k; j++) { int curr=v[j][p[j][t.id]]; sum+=a[curr][j]; } int sum2=0; for(int j=1; j<=k; j++) { int curr=v[j][p[j][id]]; 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]; /*for(int i=1; i<=k; i++) { for(int j=1; j<=n; j++) cout<<v[i][j]<<" "; cout<<endl; }*/ } 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; } } } int lvl[4000001]; map<set<int> ,int> mp; int num=0; void solve() { num++; for(int i=1; i<=k; i++) p[i][num]=1,used[v[i][1]][num]=1; q.push(num); while(1) { int id=q.top().id; q.pop(); int in=0,lf=0; for(int i=1; i<=n; i++) if(!used[i][id]) { lf++; } set<int> s; for(int i=1; i<=k; i++) s.insert(v[i][p[i][id]]); /*int hs=1; for(auto it=s.begin();it!=s.end();it++) { int b=*it; hs*=1000; hs+=b; }*/ 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][p[d][id]]][d]; //cout<<v[d][p[d][id]]<<" "<<d<<endl; } //cout<<sum<<endl; if(c<=0) { cout<<sum<<endl; return; } team nxt={-1}; for(auto it=s.begin(); it!=s.end(); it++) { num++; int i=*it; forb[i][num]=1; for(int j=1; j<=n; j++) forb[j][num]=max(forb[j][num],forb[j][id]), used[j][num]=used[j][id]; bool pos=1; for(int d=1; d<=k; d++) { while(p[d][num]<=n&&forb[v[d][p[d][num]]][num])p[d][num]++; if(p[d][num]>n)pos=0; else used[v[d][p[d][num]]][num]=1; } if(lvl[id]<=70&&pos) { team in={num}; if(nxt.id==-1||nxt<in) lvl[num]=lvl[id]+1,q.push(num); } } q.push(nxt); } } 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...