Submission #1319383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319383		Trisanu_Das	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	0 ms	332 KiB

souvenirs

#include <bits/stdc++.h>
using namespace std;

pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    vector<long long> P(N, -1);
    vector<long long> got(N, 0);
    P[0] = P0;
    long long sum_known = 0;

    for (int i = N - 1; i >= 1; --i) {
        long long M = P0 - 1 - sum_known;
        if (M < 0) M = 0;

        auto res = transaction(M);
        auto &L = res.first;
        long long R = res.second;

        long long paid = M - R;

        vector<bool> seen(N, false);
        for (int t : L) {
            got[t]++;
            seen[t] = true;
        }

        long long subtract = 0;
        for (int j = i + 1; j < N; ++j)
            if (seen[j])
                subtract += P[j];

        long long Pi = paid - subtract;
        P[i] = Pi;

        sum_known += Pi;
    }
    for (int i = 1; i < N; ++i) {
        long long need = i - got[i];
        while (need > 0) {
            transaction(P[i]);
            --need;
        }
    }
}

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