제출 #1263495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263495		abdelhakim	축제 (IOI25_festival)	C++20	100 / 100	268 ms	130332 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)1e17
#define dbg(x) cerr<<#x<<' ' << x << endl;
using namespace std;

ll maxans(ll val, vector<vector<ll>>& ones)
{
  ll ans=ones.size();
  ll sm=0;
  for (int i=0;i<ones.size();i++)
  {
    sm+=ones[i][0];
    if(sm>val)
    {
      return i;
    }
  }
  return ans;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  ll n=P.size();
  ll aa=A;
  vector<vector<ll>> pr1(P.size());
  for (int i=0;i<n;i++)
  {
    pr1[i]={P[i],T[i],i};
  }
  auto comparator = [](vector<ll> a, vector<ll> b)
  {
    ll val1=a[0]*a[1]*b[1]+b[0]*b[1];
    ll val2= b[0]*a[1]*b[1] + a[0]*a[1];
    if(val1==val2)
    {
      return a[0] < b[0];
    }
    return val1 < val2;
  };
  sort(pr1.begin(), pr1.end(),comparator);
  vector<int> ans;
  vector<vector<ll>> pr;
  for (int i=0;i<n;i++)
  {
    if((aa-pr1[i][0])*pr1[i][1] >= aa)
    {
      aa=(aa-pr1[i][0])*pr1[i][1];
      aa=min(aa,(ll)1e16);
      ans.push_back(pr1[i].back());
    }
    else
    {
      pr.push_back(pr1[i]);
    }
  }
  
  n=pr.size();
  vector<vector<ll>> ones;

  while(pr.size() && pr.back()[1]==1)
  {
    ones.push_back(pr.back());
    pr.pop_back();
  }
 
  reverse(ones.begin(), ones.end());

  n=pr.size();
  vector<vector<pair<ll,ll>>> dp(n,vector<pair<ll,ll>>(31,{-1,-1}));
  for (int i=0;i<n;i++)
  {
    for (int j=0;j<=dp[i].size()-1;j++)
    {
      if(j==0)
      {
        dp[i][j]={aa,-1};
      } 
      else if(i==0)
      {
        if(j==1 && pr[i][0] <= aa)
        {
          dp[i][j].first=min((aa-pr[i][0])*pr[i][1],(ll)1e16);
          dp[i][j].second=i;
        }
      }
      else
      { 
        dp[i][j]=dp[i-1][j];
        if(pr[i][0]<=dp[i-1][j-1].first)
        {
          ll val=min((ll)1e16,(dp[i-1][j-1].first-pr[i][0])*pr[i][1]);
          if(val > dp[i][j].first)
          {
            dp[i][j]={val,i};
          }
        }
      }
    }
  }
  pair<ll,ll> bad={-1,-1};
  ll bestans=0;
  if(n!=0)
  {for (int i=dp[0].size()-1;i>=0;i--)
  {
    if(dp[n-1][i]!=bad)
    {
      bestans=max(bestans,i+maxans(dp[n-1][i].first,ones));
    }
  }}
  ll index=maxans(aa,ones);
  if(index >= bestans)
  {
    for (int i=0;i<index;i++)
    {
      ans.push_back(ones[i].back());
    }
  }
  else
  {
    ll val=0;
    vector<ll> ans2;
    for (int i=dp[0].size()-1;i>=0;i--)
    {
      ll val1=maxans(dp[n-1][i].first,ones);
      if(dp[n-1][i]!=bad && val1+i==bestans)
      {
        val=val1;
        ll cur=n-1;
        while(i)
        {
          ans2.push_back(pr[dp[cur][i].second].back());
          cur=dp[cur][i].second-1;
          i--;
        }
        break;
      }
    }
    for (int i=ans2.size()-1;i>=0;i--)
    {
      ans.push_back(ans2[i]);
    }
    for (int j=0;j<val;j++)
    {
      ans.push_back(ones[j].back());
    }
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18