Submission #1305248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305248		peteza	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	400 KiB

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
using ll = long long;

/*
int costs[5] = {30,21,20,15,6};

pair<vector<int>, ll> transaction(ll m) {
	vector<int> res;
	for(int i=0;i<5;i++) {
		if(costs[i]<=m) {
			res.push_back(i);
			m -= costs[i];
		}
	}
	return {res, m};
}*/

int n;
void rec(vector<int>&cnt, vector<ll>&cost, int idx, ll cc) {
	if(idx>=n) return;
	if(~cost[idx]) return;
	auto res = transaction(cc-1);
	idx = res.first.front();
	for(auto&e:res.first)cnt[e]++;
	while(res.first.size() > 1) {
		if(!(~cost[res.first.back()])) {
			rec(cnt, cost, res.first.back(), (cc-1-res.second)/res.first.size()+1);
		}
		res.second += cost[res.first.back()];
		res.first.pop_back();
	}
	//cout << idx << "->" << cc-1 << "\n";
	cost[idx] = cc-1-res.second;
	rec(cnt, cost, idx+1, cost[idx]);
}

void buy_souvenirs(int n, ll p0) {
	::n=n;
	vector<int> cnt(n);
	vector<ll> cost(n, -1);
	cost[0]=p0;
	rec(cnt, cost, 1, p0);
	for(int i=0;i<n;i++) {
		//cout << cost[i] << " ";
		while(cnt[i]<i) {
			cnt[i]++;
			transaction(cost[i]);
		}
	}
}

/*
int main() {
	// your code goes here
	buy_souvenirs(5, 30);
	return 0;
}*/

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33