Submission #1263480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263480		abdelhakim	Festival (IOI25_festival)	C++20	21 / 100	244 ms	119344 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();
  vector<vector<ll>> pr(P.size());
  for (int i=0;i<n;i++)
  {
    pr[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(pr.begin(), pr.end(),comparator);
  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]={A,-1};
      } 
      else if(i==0)
      {
        if(j==1 && pr[i][0] <= A)
        {
          dp[i][j].first=min((A-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};
  vector<int> ans;
  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(A,ones);
  if(index >= bestans)
  {
    for (int i=0;i<index;i++)
    {
      ans.push_back(ones[i].back());
    }
  }
  else
  {
    ll val=0;
    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)
        {
          ans.push_back(pr[dp[cur][i].second].back());
          cur=dp[cur][i].second-1;
          i--;
        }
        break;
      }
    }
    reverse(ans.begin(), ans.end());
    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: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 16 / 16
• Subtask 7: 0 / 18