Submission #1265747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265747		SHZhang	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	11 ms	408 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cstdlib>
#include <cstdio>

using namespace std;

#define ll long long

int n;

ll price[105];
int uses[105];

int solve(int right, ll spend)
{
    pair<vector<int>, ll> result = transaction(spend);
    for (int x: result.first) {
        uses[x]++;
    }
    int left = result.first[0];
    ll amt_spent = spend - result.second;
    while (result.first.back() > right) {
        amt_spent -= price[result.first.back()];
        result.first.pop_back();
    }
    if (left < right) {
        while (true) {
            int left2 = solve(right, (amt_spent - 1LL) / (ll)(result.first.size()));
            while (result.first.back() >= left2) {
                amt_spent -= price[result.first.back()];
                result.first.pop_back();
            }
            if (left2 == left + 1) break;
            right = left2 - 1;
        }
    }
    price[left] = amt_spent;
    return left;
}

void buy_souvenirs(int N, ll P0) {
    n = N;
    solve(n - 1, P0 - 1);
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= i - uses[i]; j++) {
            transaction(price[i]);
        }
    }
}

• 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