Submission #418608

#	Time	Username	Problem	Language	Result	Execution time	Memory
418608		abdzag	Olympiads (BOI19_olympiads)	C++17	0 / 100	2 ms	716 KiB

olympiads

#include<bits/stdc++.h>
//#include"tickets.h"
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf = 1e9;

using namespace std;

ll choose(ll n, ll k) {
	if (n == 0)return 0;
	if (k == 0)return 1;
	if (k == n)return 1;
	ll ans = 1;
	rrep(i, n, (n-k) ) {
		ll ny = i;
		ans *= ny;
	}
	rep(i, 1, k + 1)ans /= i;
	return ans;
}
vector<vector<ll>> choices(501, vector<ll>(7));
int main() {
	cin.sync_with_stdio(false);
	ll n, c, k;
	rep(i, 0, 501) {
		rep(j, 0, 6) {
			if (i < j)continue;
			ll val = choose(i, j);
			if (val > 1e9)break;
			choices[i][j] = val;
		}
	}
	cin >> n >> k >> c;
	vector<vector<ll>> v(n, vector<ll>(k));
	rep(i, 0, n)rep(j, 0, k)cin >> v[i][j];
	vector < vector<pair<ll, ll>>> vec(k);
	rep(i, 0, n) {
		rep(j, 0, k) {
			vec[j].emplace_back(v[i][j], i);
		}
	}
	trav(a, vec)sort(all(a),greater<>());
	map<vector<int>, bool> mp;
	vector<int> cur(k);
	ll val = 0;
	vector<vector<int>> sorted;
	bitset<501> present;
	ll mising = k;
	rep(i, 0, k) {
		if (!present[vec[i][cur[i]].second]) {
			mising--;
			present[vec[i][cur[i]].second] = 1;
		}
	}
	val += choices[n - (k - mising)][mising];
	mp[cur] = 1;
	ll order = 0;
	while (val<c) {
		bool done = true;

		vector<int> cur2=cur;
		rep(i, 0, k) {
			cur2[i]++;
			done = mp[cur2];
			cur2[i]--;
		}
		if (done) {
			cur = sorted[order++];
		}
		vector<int> init(k, inf);
		pair<ll, vector<int>> best=make_pair(inf,init);
		rep(i, 0, k) {
			cur2 = cur;
			bool bad = false;
			while (mp[cur2]) {
				cur2[i]++;
				if (cur2[i] == k) {
					bad = true;
					break;
				}
				//rep(j, 0, cur.size()) {
				//	if (i == j)continue;
				//	if(vec[j][cur2[j]].second == vec[i][cur2[i]].second)
				//}
			}
			if (bad)continue;
			rep(j, 0, k) {
				if (j == i)continue;
				if (vec[j][cur[j]].second == vec[i][cur[i]].second) {
					cur2[j]++;
					while (mp[cur2]) {
						cur2[j]++;
						if (cur2[j] == k) {
							bad = true;
							break;
						}
					}
				}
				if (bad) {
					break;
				}
			}
			if (bad)continue;
			pair<ll, vector<int>> local = make_pair(0, cur2);
			rep(j, 0, k) {
				local.first += vec[j][cur[j]].first - vec[j][cur2[j]].first;
			}
			best = min(best, local);
		}
		cur2 = best.second;
		sorted.push_back(cur2);
		mp[cur2] = 1;
		ll howmany = n;
		bitset<501> visited;
		bitset<501> present;
		rep(i, 0, k) {
			rrep(j, cur2[i], -1) {
				if (!visited[vec[i][j].second]) {
					howmany--;
					visited[vec[i][j].second] = 1;
				}
			}
		}
		ll mising = k;
		rep(i, 0, k) {
			if (!present[vec[i][cur2[i]].second]) {
				mising--;
				present[vec[i][cur2[i]].second] = 1;
			}
		}
		val += choices[howmany][mising];
		if (val >= c)cur = cur2;
	}
	ll ans = 0;
	rep(i, 0, k) {
		ans += vec[i][cur[i]].first;
	}
	cout << ans << endl;
	return 0;
}

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