Submission #1252514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252514		anfi	선물 (IOI25_souvenirs)	C++20	25 / 100	11 ms	420 KiB

souvenirs

#include"souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const long long inf = 1e9;
long long n,last,p[105],cn[105];
long long hitung(long long s, long long k){
    s += (long long)k*(k-1)/2+k-1;
    return s/k;
}

void fin(long long initial_money) {
    vector<long long> money_stack;
    vector<vector<int>> v_stack;
    vector<long long> sum_stack;
    vector<int> stage_stack;

    money_stack.push_back(initial_money);
    v_stack.emplace_back();
    sum_stack.push_back(0);
    stage_stack.push_back(0);

    while (!money_stack.empty()) {
        int d = money_stack.size() - 1;

        if (stage_stack[d] == 0) {
            auto [v, remain] = transaction(money_stack[d]);
            long long sum = money_stack[d] - remain;

            if (!v.empty() && v[0] < last) {
                while (!v.empty() && v.back() >= last) {
                    sum -= p[v.back()];
                    v.pop_back();
                }
            }

            v_stack[d] = v;
            sum_stack[d] = sum;

            for (int i : v) cn[i]++;

            if (!v.empty() && v[0] < last && v[0] + 1 != last) {
                stage_stack[d] = 1;
                long long new_money = hitung(sum, v.size()) - 1;
                money_stack.push_back(new_money);
                v_stack.emplace_back();
                sum_stack.push_back(0);
                stage_stack.push_back(0);
                continue;
            }

            stage_stack[d] = 1;
        }

        if (stage_stack[d] == 1) {
            if (!v_stack[d].empty()) {
                int idx = v_stack[d][0];
                p[idx] = sum_stack[d];
                last = idx;
            }

            money_stack.pop_back();
            v_stack.pop_back();
            sum_stack.pop_back();
            stage_stack.pop_back();
        }
    }
}



void buy_souvenirs(int N, long long p0){ 
    memset(cn, 0, sizeof(cn));
    memset(p, 0, sizeof(p));
    p[0] = p0, n = N; last = N;
    fin(p0-1);
    for(int i = 1; i < N; i++){
        while(cn[i] < i){
            transaction(p[i]);
            cn[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