Submission #954625

#TimeUsernameProblemLanguageResultExecution timeMemory
954625hengliaoOlympiads (BOI19_olympiads)C++17
44 / 100
801 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 int ll; const ll inf=1e9; 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; vll a[mxN]; vector<pll> v[6]; bool use[mxN]; 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[j][i]); } re+=cur; } return re; } void solve(){ memset(use, 0, sizeof(use)); cin>>n>>k>>c; for(ll i=0;i<k;i++){ v[i].resize(n); } for(ll i=0;i<n;i++){ a[i].resize(k); for(ll j=0;j<k;j++){ cin>>v[j][i].F; v[j][i].S=i; a[i][j]=v[j][i].F; } } for(ll i=0;i<k;i++){ sort(v[i].begin(), v[i].end(), greater<pll>()); } set<ll> in; ll mx=0; for(ll i=0;i<k;i++){ in.insert(v[i][0].S); mx+=v[i][0].F; use[v[i][0].S]=1; } while((ll)in.size()<k){ for(ll i=0;i<n;i++){ if(!use[i]){ in.insert(i); use[i]=1; break; } } } priority_queue<pair<ll, set<ll>>> pq; map<set<ll>, bool> done; //cout<<'\n'; //cout<<re<<'\n'; pq.push({mx, in}); done[in]=1; ll ans; //cout<<mx<<'\n'; //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 it3:nxt){ for(ll j=0;j<k;j++){ cur[j]=max(cur[j], a[it3][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][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; }

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:176:16: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |     cout<<ans<<'\n';
      |                ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...