Submission #1258600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258600		Samuraj	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 107;
int ile[max_n];
ll c[max_n];

void get_c(int n, ll val){
    //cout << "\nget_c, val: " << val << '\n';
    pair<vi,ll> v = transaction(val);
    for(auto x:v.st) ile[x]++;

    ll whole_cost = val-v.nd;
    //cout << "whole_cost: " << whole_cost << " v.st: ";
    //for(auto x:v.st) cout << x << ' ';
    //cout << '\n';

    if(v.st.size() == 1){
        //cout << "size = 1\n";
        c[v.st[0]] = whole_cost;
        if(!c[v.st[0]+1] && v.st[0] != n-1) get_c(n,whole_cost-1);
        return;
    }

    //dopoki nie mamy kolejnego kosztu!    
    while(!c[v.st[1]]){
        ll s = 0; ll new_val = whole_cost;
        for(auto x:v.st){
            if(c[x]) new_val -= c[x];
            else s++;
        }
        //cout << "\npetla dla val: " << val << " s: " << s << " new_val: " << new_val << '\n'; 

        ll max_a = ((new_val+s*(s-1)/2)/s);
        //cout << "max_a: " << max_a << '\n';
        get_c(n,max_a-1); //nie wiadomo czy ten -1 dziala!
    }
    
    for(auto x:v.st) whole_cost -= c[x];
    c[v.st[0]] = whole_cost;
    //cout << "\ndla val: " << val << " ustawiamy c od: " << v.st[0] << " na " << whole_cost << '\n';
    
    if(!c[v.st[0]+1] && v.st[0] != n-1) get_c(n,c[v.st[0]]-1);
    return;
}

void buy_souvenirs(int n, ll p0){
    get_c(n,p0-1);
    rep(i,1,n-1){
        //cout << "i: " << i << " c: " << c[i] << '\n';
        while(ile[i] < i){
            ile[i]++;
            transaction(c[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