Submission #954634

#TimeUsernameProblemLanguageResultExecution timeMemory
954634hengliaoOlympiads (BOI19_olympiads)C++17
44 / 100
1683 ms262144 KiB
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; const ll A=9828401843; const ll B=1e9+78328738; const ll inf=1e17; struct team{ vll v; ll n, id; void init(ll tn){ n=tn; v=vll(n, -inf); } void rd(ll tn){ n=tn; v.resize(n); for(ll i=0;i<n;i++){ cin>>v[i]; } } void mxwith(vll &cur){ for(ll i=0;i<n;i++){ cur[i]=max(cur[i], v[i]); } } void operator=(const team &tar){ for(ll i=0;i<n;i++){ v[i]=tar.v[i]; } id=tar.id; } bool operator<(const team &tar) const{ return id<tar.id; } }; const ll mxN=505; ll n, k, c; vector<team> a; vector<team> on; vector<team> best; bool use[mxN]; unordered_map<ll, ll> done; ll hs(const vll &tar){ ll re=0; vll tep=tar; sort(tep.begin(), tep.end()); for(ll i=0;i<k;i++){ re=(re*A+tep[i])%B; } return re; } ll gt(vector<team> &tar, vll &cur){ for(ll i=0;i<k;i++){ tar[i].mxwith(cur); } ll re=0; for(ll i=0;i<k;i++){ re+=cur[i]; } return re; } ll gt2(vll &tar){ ll re=0; for(ll i=0;i<k;i++){ ll cur=0; for(ll j=0;j<k;j++){ cur=max(cur, a[tar[j]].v[i]); } re+=cur; } return re; } void solve(){ memset(use, 0, sizeof(use)); cin>>n>>k>>c; a.resize(n); for(ll i=0;i<k;i++){ team tep; tep.init(k); best.pb(tep); } for(ll i=0;i<n;i++){ a[i].rd(k); a[i].id=i; } for(ll i=0;i<n;i++){ for(ll j=0;j<k;j++){ if(a[i].v[j]>best[j].v[j]){ best[j]=a[i]; } } } ll cnt=0; vector<team> be; for(ll i=0;i<k;i++){ if(use[best[i].id]){ cnt++; } else{ use[best[i].id]=1; be.pb(best[i]); } } while(cnt--){ for(ll i=0;i<n;i++){ if(!use[i]){ be.pb(a[i]); use[i]=1; break; } } } priority_queue<pair<ll, vll>> pq; vll cur(k, -inf); ll re=gt(be, cur); vll tep; for(ll i=0;i<n;i++){ if(use[i]){ tep.pb(i); //cout<<i<<' '; } } //cout<<'\n'; //cout<<re<<'\n'; pq.push({re, tep}); done[hs(tep)]++; ll ans; //assert(1); //bool b=0; vll cur2; for(ll i=0;i<c && !pq.empty();i++){ pair<ll, vll> now=pq.top(); pq.pop(); ans=now.F; vll tep=now.S; memset(use, 0, sizeof(use)); for(ll j=0;j<k;j++){ use[tep[j]]=1; } for(ll pos=0;pos<k;pos++){ vll nxt; for(ll j=0;j<k;j++){ if(j==pos) continue; //assert(tep[j]<n); /*if(tep[j]>=n){ cout<<"bad "<<i<<'\n'; for(auto it:tep){ cout<<it<<' '; } cout<<'\n'; b=1; break; }*/ nxt.pb(tep[j]); } //if(b) break; cur=vll(k, -inf); for(auto it:nxt){ for(ll j=0;j<k;j++){ cur[j]=max(cur[j], a[it].v[j]); } } for(ll j=0;j<n;j++){ if(!use[j]){ nxt.pb(j); ll h=hs(nxt); if(done[h]){ nxt.pop_back(); } else{ done[h]++; cur2=cur; for(ll ii=0;ii<k;ii++){ cur2[ii]=max(cur2[ii], a[j].v[ii]); } ll re=0; for(ll ii=0;ii<k;ii++){ re+=cur2[ii]; } pq.push({re, nxt}); nxt.pop_back(); } //done.insert(hs(nxt)); } } } } cout<<ans<<'\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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...