Submission #1319351

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

souvenirs

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

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

    for (int i = N - 1; i >= 1; --i) {
        long long S = 0;

        for (int j = i + 1; j < N; ++j) {
            if (P[j] != -1)
                S += (long long)(j - i) * P[j];
        }

        long long M = P0 - 1 - S;
        if (M < 0) M = 0;

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

        long long paid = M - R;

        long long known_sum = 0;
        vector<bool> inL(N, false);

        for (int t : L) {
            inL[t] = true;
            got[t]++;
        }

        for (int j = i + 1; j < N; ++j)
            if (inL[j] && P[j] != -1)
                known_sum += P[j];
        long long Pi = paid - known_sum;
        P[i] = 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