Submission #1249659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249659		QwertyPi	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	13 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], eq[N_MAX][N_MAX];
int sum[N_MAX], P[N_MAX];

int _transaction(int pay) {
    auto [C, rem] = transaction(pay);
    assert(!C.empty());
    for (int i = 0; i < (int) C.size(); i++) {
        used[C[0]][C[i]] = eq[C[0]][C[i]] = true;
    }
    int cost = pay - rem;
    sum[C[0]] = cost;
    return C[0];
}

void solve(int N) {
    if (N == 0) return;

    int prv = -1, cnt = 1;
    for (int j = N - 1; j >= 0; j--) {
        if (eq[j][j]) {
            prv = j;
            cnt = accumulate(eq[j] + j, eq[j] + N, 0LL);
            break;
        }
    }
    assert(prv >= 0);
    while (prv < N - 1) {
        int r = _transaction((sum[prv] - 1) / cnt);
        prv = r;
    }
    P[N - 1] = sum[N - 1];
    for (int i = 0; i < N; i++) {
        if (eq[i][N - 1]) eq[i][N - 1] = false, sum[i] -= P[N - 1];
    }
    solve(N - 1);
}

void buy_souvenirs(int32_t N, int P0) {
    eq[0][0] = 1; sum[0] = P[0] = P0;
    solve(N);
    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: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33