Submission #388182

#TimeUsernameProblemLanguageResultExecution timeMemory
388182leakedOlympiads (BOI19_olympiads)C++14
0 / 100
136 ms262148 KiB
#include <bits/stdc++.h> //#pra #define sz(x) (int)x.size() #define vec vector #define pb push_back #define rall(x) x.rbegin(),x.rend() #define pii pair<int,int> #define f first #define s second using namespace std; const int N=3e2+3; typedef unsigned long long ull; auto rnd=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0))); ull r[N]; struct buben{ int sum; vec<int>vc; buben(); buben(int _a,vec<int> _vc) : sum(_a),vc(_vc) {} const bool operator<(const buben &o) const{ if(o.sum!=sum) return sum<o.sum; return true; } }; signed main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m,k; cin>>n>>m>>k; /// i suppose it's n*m*k*log vec<vec<int>>a(n,vec<int>(m)); vec<vec<pii>>hah(m); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; hah[j].pb({a[i][j],i}); } } for(int i=0;i<m;i++) sort(rall(hah[i])); priority_queue<buben>pq; map<ull,bool>mp; map<vec<int>,bool>mp2; vec<int>lol(m,0); buben me(0,lol); for(int j=0;j<m;j++) me.sum+=hah[j][me.vc[j]].f; pq.push(me); vec<int>used(n,0); int cr=0; for(int i=0;i<n;i++) r[i]=rnd(); while(!pq.empty()){ // cerr<<c.sum<<endl; auto c=pq.top();pq.pop(); // cerr<<c.sum<<endl; if(mp2.count(c.vc)) continue; // cerr<<c.sum<<endl; cr++; mp2[c.vc]=1; ull hs=0; for(int j=0;j<m;j++) { if(used[hah[j][c.vc[j]].s]!=cr){ hs+=r[hah[j][c.vc[j]].s]; used[hah[j][c.vc[j]].s]=cr; } } if(mp.count(hs)==0){ mp[hs]=1; // cerr<<c.sum<<endl; // for(int j=0;j<m;j++) cerr<<hah[j][c.vc[j]].s+1<<' '; // cerr<<endl; k--; if(k==0){ cout<<c.sum<<endl; return 0; } } buben nw=c; for(int i=0;i<k;i++){ nw.sum-=hah[i][nw.vc[i]].f; nw.vc[i]++; if(nw.vc[i]!=n){ int mx=0; for(int j=0;j<k;j++){ mx=max(mx,a[hah[j][nw.vc[j]].s][i]); } nw.sum+=mx; pq.push(nw); nw.sum-=mx; } nw.vc[i]--; nw.sum+=hah[i][nw.vc[i]].f; } } 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...