Submission #1255183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255183		yuichiro17	선물 (IOI25_souvenirs)	C++20	100 / 100	13 ms	420 KiB

souvenirs

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

ll price[100];
int cnt[100],n;

tuple<vector<bool>,ll,int,ll> buy(ll x){
  auto [v,p]=transaction(x);
  vector<bool>v1(n,false);
  for(int i:v){cnt[i]++;v1[i]=true;}
  return{v1,x-p,v.size(),v[0]};
}

void dfs(ll x){
  auto [v,p,c,v0]=buy(x);
  do{
    for(int i=v0+1;i<n;i++){
      if(price[i]!=-1&&v[i]){
        v[i]=false;
        p-=price[i];
        c--;
      }
    }
    if(c==1){
      price[v0]=p;
      bool flag=false;
      for(int i=v0+1;i<n;i++){
        if(price[i]==-1){flag=true;break;}
      }
      if(flag)dfs(p-1);
      return;
    }
    dfs(p/c);
  }while(c!=1);
}

void buy_souvenirs(int N, long long P0) {
  n=N;
  for(int i=0;i<n;i++){price[i]=-1;cnt[i]=0;}
  price[0]=P0;
  dfs(P0-1);
  for(int i=1;i<n;i++){
    for(int j=cnt[i];j<i;j++){
      buy(price[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