제출 #1280736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280736		SabaKharebava	축제 (IOI25_festival)	C++20	100 / 100	77 ms	9656 KiB

festival

#include"festival.h"
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const long long mx = 1e17;

vector<int> cur, best;
int best_type1;

void solve(int pos, long long tokens, int lim, vector<int> &a, vector<pair<long long, int>> &b, vector<int> &p, vector<int> &t) {
	if (lim == 1 or pos == a.size()) {
		int it = lower_bound(b.begin(), b.end(), make_pair(tokens+1, -1)) - b.begin();
		if (it + cur.size() > best.size() + best_type1) {
			best = cur;
			best_type1 = it;
		}
		return;
	}

	if (tokens >= p[a[pos]] and lim >= t[a[pos]]) {
		cur.pb(a[pos]);
		solve(pos + 1, min((tokens - p[a[pos]]) * t[a[pos]], mx), lim, a, b, p, t);
		cur.pop_back();
	}
	solve(pos + 1, tokens, min(lim, t[a[pos]]-1), a, b, p, t);
}

vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
	vector<int> a;
	vector<pair<long long, int>> b;
	
	for (int i = 0; i < p.size(); i++) {
		if (t[i] == 1)
			b.pb({p[i], i});
		else
			a.pb(i);
	}

	sort(a.begin(), a.end(), [&](int a, int b) {
		if (t[a] == t[b])
			return p[a] < p[b];
		return 1ll * p[a] * t[a] * (t[b] - 1) < 1ll * p[b] * t[b] * (t[a] - 1);
	});
	sort(b.begin(), b.end());
	for (int i = 1; i < b.size(); i++)
		b[i].first += b[i-1].first;

	vector<int> res;
	long long cur = A;

	for (int e : a) {
		if ((cur-p[e]) * t[e] > cur) {
			cur = min(mx, (cur-p[e]) * t[e]);
			res.pb(e);
		} else
			break;
	}
	a.erase(a.begin(), a.begin() + res.size());

	solve(0, cur, 4, a, b, p, t);

	for (int e : best)
		res.pb(e);
	for (int i = 0; i < best_type1; i++)
		res.pb(b[i].second);
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18