Submission #1286439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286439		matere	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
long long ans[105],tb[105],kn=0;
void find_ans(long long i){
    pair<vector<int>,long long>res = transaction(i);
    for(int i:res.first) tb[i]++;
    while(res.first.back()>=kn){
        res.second+=ans[res.first.back()];
        res.first.pop_back();
    }
    while(res.first.size()>1){
        find_ans((i-res.second)/res.first.size());
        while(res.first.back()>=kn){
            res.second+=ans[res.first.back()];
            res.first.pop_back();
        }
    }
    ans[res.first[0]]=i-res.second;
    if(kn!=res.first[0]+1) find_ans(ans[res.first[0]]-1);
    kn=res.first[0];
}
void buy_souvenirs(int n, long long P0){
    kn=n;
    ans[0]=P0;
    find_ans(P0-1);
    for(int i=1;i<n;i++) while(tb[i]<i){
        transaction(ans[i]);
        tb[i]++;
    }
    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