Submission #1249465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249465		bronze_coder	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;

void buy_souvenirs(int N, long long P0){
    vector<vector<long long>> answers(N);
    vector<int> count(N,0);
    for(int i=0;i<N;i++){
        vector<long long> x(N+2,0);
        answers[i] = x;
    }
    answers[0][0] = 1;
    answers[0][N] = P0;
    answers[0][N+1] = 1;

    vector<long long> cost(N,-1);
    for(int i=N-1;i>=0;i--){
        for(int j=i;j>=0;j--){
            if(answers[j][N+1]>0){
                int index = j;
                while(index<i){
                    long long c = (answers[index][N]-1)/answers[index][N+1];
                    pair<vector<int>, long long> x = transaction(c);
                    vector<int> a = x.first;
                    vector<long long> b(N+2,0);
                    b[N+1] = a.size();
                    b[N] = c-x.second;
                    for(int z:a){
                        b[z] = 1;
                        count[z]++;
                    }
                    for(int k=i+1;k<N;k++){
                        if(b[k]){
                            b[k] = 0;
                            b[N] -= cost[k];
                            b[N+1]--;
                        }
                    }
                    index = a[0];
                    answers[index] = b;
                }
                break;
            }
        }
        cost[i] = answers[i][N];
        for(int j=0;j<i;j++){
            if(answers[j][i]){
                answers[j][N+1]--;
                answers[j][N] -= cost[i];
                answers[j][i] = 0;
            }
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<i-count[i];j++){
            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