Submission #1249651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249651		QwertyPi	선물 (IOI25_souvenirs)	C++20	25 / 100	12 ms	416 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N_MAX = 100 + 11;
bool used[N_MAX][N_MAX];
int sum[N_MAX], P[N_MAX];

void buy_souvenirs(int32_t N, int P0) {
    int prv = P0, cnt = 1; P[0] = P0;
    while (true) {
        int val = (prv - 1) / cnt;
        auto [C, rem] = transaction(val);
        int cost = val - rem;
        assert(!C.empty());
        for (int i = 0; i < C.size(); i++) {
            used[C[0]][C[i]] = true;
        }
        sum[C[0]] = cost;
        prv = cost, cnt = C.size();
        if (C[0] == N - 1) break;
    }
    for (int i = N - 1; i >= 1; i--) {
        if (used[i][i]) {
            int s = sum[i];
            for (int j = i + 1; j < N; j++) {
                if (used[i][j]) s -= P[j];
            }
            P[i] = s;
        } else {

        }
    }

    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j++) {
            if (!used[i][j]) {
                transaction(P[j]);
            }
        }
    }
}

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