Submission #1307802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307802		exoworldgd	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	420 KiB

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,cnt[N];
ll cost[N];
void rec(int idx,ll cc){
    if(idx>=n||~cost[idx])return;
    auto res=transaction(cc-1);
    int cur=res.first.front();
    for(auto&e:res.first)cnt[e]++;
    while(res.first.size()>1){
        if(!(~cost[res.first.back()]))rec(res.first.back(),(cc-1-res.second)/res.first.size()+1);
        res.second+=cost[res.first.back()],res.first.pop_back();
    }
    cost[cur]=cc-1-res.second,rec(cur+1,cost[cur]);
}
void buy_souvenirs(int N,ll P){
    n=N;
    for(int i=0;i<n;i++)cost[i]=-1;
    cost[0]=P,rec(1,P);
    for(int i=0;i<n;i++)while(cnt[i]<i)cnt[i]++,transaction(cost[i]);
}

• 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