제출 #1252569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252569		anfi	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	12 ms	424 KiB

souvenirs

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

static const int MAXN = 105;
int n, last_idx;
ll p[MAXN];
int cnt_visit[MAXN];

struct Frame {
    ll money;
    vector<int> v;
    ll sum;
    int stage;  
};

ll calc_next(ll s, int k) {
    s += (ll)k * (k - 1) / 2 + k - 1;
    return s / k;
}

void build_iterative(ll initial_money) {
    vector<Frame> stk;
    stk.reserve(MAXN);
    stk.push_back({initial_money, {}, 0, 0});

    while (!stk.empty()) {
        Frame &f = stk.back();
        if (f.stage == 0) {
            auto [v, remain] = transaction(f.money);
            ll s = f.money - remain;

            while (!v.empty() && v.back() >= last_idx) {
                s -= p[v.back()];
                v.pop_back();
            }

            f.v = move(v);
            f.sum = s;
            for (int idx : f.v) cnt_visit[idx]++;

            if (!f.v.empty() && f.v[0] < last_idx && f.v[0] + 1 != last_idx) {
                ll next_money = calc_next(f.sum, f.v.size()) - 1;
                f.stage = 1;  
                stk.push_back({next_money, {}, 0, 0});
                continue;
            }

            f.stage = 1;
        } else {
            if (!f.v.empty()) {
                int idx = f.v[0];
                p[idx] = f.sum;
                last_idx = idx;
            }
            stk.pop_back();
        }
    }
}

void buy_souvenirs(int N, ll P0) {
    n = N;
    last_idx = N;
    memset(p, 0, sizeof(p));
    memset(cnt_visit, 0, sizeof(cnt_visit));

    p[0] = P0;
    build_iterative(P0 - 1);

    for (int i = 1; i < n; ++i) {
        while (cnt_visit[i] < i) {
            transaction(p[i]);
            cnt_visit[i]++;
        }
    }
}

• 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