Submission #1250304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250304		8e7	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	1188 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};

int counts[105];
void solve(int n, int cur, vector<vector<int>> coef, vector<ll> sums, vector<ll> &given) {
    //debug("solve", n, cur);
    while (n >= cur) {
        vector<int> last = coef.back();
        ll val = sums.back(); 
        ll que;
        if (last.size() == 1) {
            given[cur] = val;
            que = val - 1;
            if (cur == n) break;
        } else {
            que = val / last.size();
        }
        auto [terms, rem] = transaction(que); 
        //debug(que);
        //pary(terms.begin(), terms.end());
        assert(terms.size() > 0);
        for (int i:terms) counts[i] += 1;
        int cur_rec = terms[0];
        vector<vector<int>> coef_rec = coef;
        vector<ll> sums_rec = sums;

        ll result = que - rem;
        while (terms.size() > 0 && terms.back() > n) {
            result -= given[terms.back()];
            terms.pop_back();
        }
        coef_rec.push_back(terms);
        sums_rec.push_back(result);
        solve(n, cur_rec, coef_rec, sums_rec, given);
        //assume that [cur_rec, n] has been solved
        for (int i = 0;i < coef.size();i++) {
            vector<int> &v = coef[i];
            while (v.size() && v.back() >= cur_rec) {
                sums[i] -= given[v.back()];
                v.pop_back();
            }
        }
        n = cur_rec-1;
    }
    coef.pop_back();
    sums.pop_back();
}
void buy_souvenirs(int N, long long P0) {
    int n = N - 1;
    vector<vector<int>> coef_ini;
    vector<ll> sums_ini;
    coef_ini.push_back(vector<int> (1, 0));
    sums_ini.push_back(P0);
    vector<ll> given(N, 0);
    solve(n, 0, coef_ini, sums_ini, given);
    for (int i = 1;i <= n;i++) {
        while (counts[i] < i) {
            transaction(given[i]);
            counts[i] += 1;
        }
    }
    return;
}

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