제출 #1280620

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

festival

// mtlianad chemi kodi araa es

#include<bits/stdc++.h>

using namespace std;

const long long mx = 1e18;

#define pb push_back

vector<int> best, cur;
int best1 = 0;

void go(int ind, long long tok, int tt, vector<int> f, vector<long long> pref, vector<int> p, vector<int> t) {
	if (tt == 1 or ind == f.size()) {
		auto pos = lower_bound(pref.begin(), pref.end(), tok+1) - pref.begin();

		if (pos + cur.size() > best.size() + best1) {
			best1 = pos;
			best = cur;
		}

		return;
	}

	if (tok >= p[f[ind]] and tt >= t[f[ind]]) {
		cur.pb(f[ind]);
		go(ind+1, min((tok - p[f[ind]]) * t[f[ind]], mx), tt, f, pref, p, t);
		cur.pop_back();
	}
	go(ind+1, tok, min(tt, t[f[ind]]-1), f, pref, p, t);
}

vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
	long long tok = a;
	vector<int> f, s;
	for (int i = 0; i < p.size(); i++) {
		if (t[i] == 1)
			s.pb(i);
		else
			f.pb(i);
	}
	sort(f.begin(), f.end(), [&](int a, int b) {
		if (t[a] == t[b])
			return p[a] < p[b];
		else {
			long long A = -p[a] * t[a] * t[b] - p[b] * t[b];
			long long B = -p[b] * t[a] * t[b] - p[a] * t[b];

			return A > B;
		}	
	});
	sort(s.begin(), s.end(), [&](int a, int b) {
		return p[a] < p[b];	
	});

	vector<long long> pref(s.size());
	if (pref.size() >= 1)
		pref[0] = p[s[0]];
	for (int i = 1; i < s.size(); i++) {
		pref[i] = pref[i-1] + p[s[i]];
	}

	vector<int> ans;
	for (int e : f) {
		if ((tok-p[e]) * t[e] > tok) {
			ans.pb(e);
			tok = min((long long)(tok-p[e]) * t[e], mx);
		} else
			break;
	}
	s.erase(s.begin(), s.begin() + int(ans.size()));

	go(0, tok, 4, f, pref, p, t);

	for (int e : best)
		ans.pb(e);
	for (int i = 0; i < best1; i++)
		ans.pb(s[i]);

	vector<int> ans1;
	for (int i = 0; i < ans.size(); i++) {
		if (i == 0 or ans[i] != ans[i-1])			
			ans1.pb(ans[i]);
	}

	return ans1;
}

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