Submission #1250925

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

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
#define fi first 
#define se second 
#define ll long long 
using namespace std ; 
#define re exit (0); 
#define maxn 1009 
typedef pair<vector<int>,ll> Data ; 
int cnt_buy [maxn] ; 
ll p [maxn] ; 
void buy_souvenirs(int N, long long P0) {
	Data temp ; 
	map <ll,Data> answer ; 
	for ( int i = 0 ; i < N ; i ++ ) p [i] = -1 ;  
	p [0] = P0 ; 
	priority_queue<ll,vector<ll>,greater<ll>> S ; 
	S . push (P0-1) ; 
	while (!S.empty()) 
	{
		ll t = S.top() ; S.pop() ; 
		if ( !answer.count(t) ) 
		{
			answer [t] = transaction (t) ; 
			for ( auto x : answer [t].fi ) cnt_buy [x] ++ ; 
		}
		ll sum = t - answer [t].se ;
		int cnt = answer [t].fi.size () ;  
		for ( auto x : answer [t].fi ) 
		{
			if ( p [x] != - 1 ) sum -= p [x] , cnt -- ; 
		}
		if ( cnt == 1 ) 
		{
			for ( auto x : answer [t].fi ) 
			{
				if ( p [x] == - 1 ) 
				{
					p [x] = sum ;   
					if ( x + 1 < N && p [x+1] == -1 ) S . push (p[x]-1) ; 
				}
			}
		}
		else 
		{
			S . push (t) ; 
			S . push (sum/cnt) ; 
		}
		
	}
	for ( int i = 1 ; i < N ; i ++ ) 
	{
		while ( cnt_buy [i] < i ) temp = transaction (p[i]) , cnt_buy [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