Submission #801834

#	Time	Username	Problem	Language	Result	Execution time	Memory
801834		sentheta	Olympiads (BOI19_olympiads)	C++17	100 / 100	29 ms	1104 KiB

olympiads

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}











const int N = 512;
const int K = 6;
#define Array array<int,6>
#define Bitset bitset<N>
Array empMembers, empScores={-1,-1,-1,-1,-1,-1};

int n, k, c;

// {score, event, player}
V<array<int,3>> v;


int vis[N], t;


// fix = #elems in prefix that cannot be changed
struct Team{
	int sum, fix;
	Array members;
	Bitset ban;
	
	bool operator<(const Team& o)const{
		return sum < o.sum;
	}
};

void solve(){
	
	cin >> n >> k >> c;
	
	rep(i,1,n+1) rep(j,0,k){
		int x;
		cin >> x;
		v.push_back({x, j, i});
	}
	
	sort(all(v));
	reverse(all(v));
	// for(auto[x,j,i] : v) cerr << x _ j _ i << nl;
	
	priority_queue<Team> pq;
	
	{
		t++;
		int sz = 0;
		Array members=empMembers, scores=empScores;
		
		// main players
		for(auto[x,j,i] : v) if(sz<k && x>scores[j]){
			scores[j] = x;
			if(vis[i]!=t){
				vis[i] = t;
				members[sz++] = i;
				if(sz==k) break;
			}
		}
		
		// extra players
		for(auto[x,j,i] : v) if(sz<k){
			if(vis[i]!=t){
				vis[i] = t;
				members[sz++] = i;
				if(sz==k) break;
			}
		}
		
		int sum = 0;
		rep(j,0,k){
			dbg(scores[j]);
			sum += scores[j];
		}
		dbg(sum);
		for(int i : members) cerr << i << " ";
		cerr << nl;
		
		pq.push({
			sum, 0, members, Bitset()
		});
	}
	
	
	
	rep(loop,0,c-1){
		Team team = pq.top(); pq.pop();
		dbg(team.sum);
		
		int fix = team.fix;
		for(; fix<k; fix++){
			Bitset ban = team.ban;
			ban[team.members[fix]] = 1;
			
			t++;
			int sz = 0;
			Array members=empMembers, scores=empScores;
			
			// main players
			for(auto[x,j,i] : v) if(!ban[i] && sz<k && x>scores[j]){
				scores[j] = x;
				if(vis[i]!=t){
					vis[i] = t;
					members[sz++] = i;
					if(sz==k) break;
				}
			}
			
			// extra players
			for(auto[x,j,i] : v) if(!ban[i] && sz<k){
				if(vis[i]!=t){
					vis[i] = t;
					members[sz++] = i;
					if(sz==k) break;
				}
			}
			
			if(sz!=k) continue;
			
			int nwSum = 0;
			rep(j,0,k){
				nwSum += scores[j];
			}
			
			// dbg(nwSum);
			// for(int i : members) cerr << i << " ";
			// cerr << nl;
		
			pq.push({
				nwSum, fix, members, ban
			});
		}
	}
	
	int ans = pq.top().sum;
	cout << ans << nl;
	
}

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32