Submission #954618

#TimeUsernameProblemLanguageResultExecution timeMemory
954618hengliaoOlympiads (BOI19_olympiads)C++17
44 / 100
831 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, set<ll>>> pq; map<set<ll>, bool> done; vll cur(k, -inf); ll re=gt(be, cur); set<ll> tep; for(ll i=0;i<n;i++){ if(use[i]){ tep.insert(i); //cout<<i<<' '; } } //cout<<'\n'; //cout<<re<<'\n'; pq.push({re, tep}); done[tep]=1; ll ans; //assert(1); //bool b=0; for(ll i=0;i<c && !pq.empty();i++){ pair<ll, set<ll>> now=pq.top(); pq.pop(); ans=now.F; set<ll> tep=now.S; memset(use, 0, sizeof(use)); for(auto it:tep){ use[it]=1; } for(auto it:tep){ set<ll> nxt; for(auto it2:tep){ if(it2==it) 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.insert(it2); } //if(b) break; vll cur(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.insert(j); if(done[nxt]){ nxt.erase(j); } else{ done[nxt]=1; vll 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.erase(j); } //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...