Submission #1098501

#TimeUsernameProblemLanguageResultExecution timeMemory
1098501simona1230Olympiads (BOI19_olympiads)C++17
13 / 100
26 ms19692 KiB
#include <bits/stdc++.h> using namespace std; int n,k,c; int a[2048][2048]; vector<int> v[2048]; int p[32][10048]; int used[501][10048]; int forb[501][10048]; int calc[100048]; 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]; } //cout<<t.id<<" "<<id<<endl; int sum2=0; for(int j=1; j<=k; j++) { int curr=v[j][p[j][id]]; sum2+=a[curr][j]; } return sum>sum2; } }; priority_queue<team> q; int lvl[200001]; 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[2048][2048]; void prec() { for(int i=0; i<=n; i++) { for(int j=0; j<=i; j++) { if(i==0||j==0||i==j)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; 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]]); 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<<" "<<calc[id]<<endl; if(c<=0) { cout<<sum<<endl; return; } for(auto it=s.begin(); it!=s.end(); it++) { num++; int i=*it; for(int j=1; j<=n; j++) forb[j][num]=forb[j][id], used[j][num]=used[j][id], p[j][num]=p[j][id]; forb[i][num]=1; 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]<=5&&pos) { lvl[num]=lvl[id]+1; q.push(num); } else num--; } } } void slow() { vector<int> ans; if(k==3) { for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { for(int l=j+1; l<=n; l++) { int sum=0; for(int d=1; d<=k; d++) sum+=max(a[i][d],max(a[l][d],a[j][d])); ans.push_back(sum); } } } } else 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<=3)slow(); else { prec(); solve(); } 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...