제출 #1157047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157047		vako_p	Olympiads (BOI19_olympiads)	C++20	0 / 100	1 ms	576 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define debug(x) cerr << '\n' << (#x) << " is " << (x) << " -> line: " << __LINE__ << endl;
//#define cerr if(false) cerr

const int mxN = 1e6;
ll n,k,c,a[mxN][10],x[mxN][10],idx[mxN],curr,val[mxN],mx;
bool ban[mxN][10],vis[mxN][10];
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>> q;
vector<pair<ll,ll>> v[10];
map<vector<ll>,bool> mp;

void f(ll at){
	ll cnt = 0;
	for(int j = 0; j < n; j++) cnt += 1 - ban[at][j];
	if(cnt <= k) return;
	for(int i = idx[at]; i < k; i++){
		curr++;
		idx[curr] = i;
		for(int j = 0; j < n; j++) ban[curr][j] = ban[at][j];
		for(int j = 0; j < i; j++){
			x[curr][j] = x[at][j];
			vis[curr][x[curr][j]] = true;
		}
		ban[curr][x[at][i]] = true;
		for(int j = i; j < k; j++){
			for(auto it : v[j]){
				if(vis[curr][it.second] or ban[curr][it.second]) continue;
				vis[curr][it.second] = true;
				x[curr][j] = it.second;
				break;
			}
		}
		for(int j = 0; j < k; j++){
			mx = 0;
			for(int j1 = 0; j1 < k; j1++) mx = max(mx, a[x[curr][j1]][j]);
			val[curr] += mx;
		}
		q.push({val[curr], curr});
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> a[i][j];
			v[j].pb({a[i][j], i});
		}
	}
	for(int j = 0; j < k; j++){
		sort(v[j].begin(), v[j].end());
		reverse(v[j].begin(), v[j].end());
		for(auto it : v[j]){
			if(vis[curr][it.second]) continue;
			vis[curr][it.second] = true;
			val[curr] += v[j][0].first;
			x[curr][j] = it.second;
			break;
		}
	}
	q.push({val[curr], curr});
	vector<ll> vv;
	while(!q.empty()){
		c--;
		ll at = q.top().second; q.pop();
		if(!c){
			cout << val[at] << '\n';
			break;
		}
		f(at);
		vv.clear();
		for(int i = 0; i < k; i++) vv.pb(x[at][i]);
		sort(vv.begin(), vv.end());
		assert(!mp[vv]);
		mp[vv] = true;		
	}
}

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