Submission #1263377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263377		abdelhakim	Festival (IOI25_festival)	C++20	22 / 100	1048 ms	2162688 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;
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];
    return val1 < val2;
  };
  sort(pr.begin(), pr.end(),comparator);
  vector<vector<pair<ll,ll>>> dp(n,vector<pair<ll,ll>>(n+1,{-1,-1}));
  for (int i=0;i<n;i++)
  {
    for (int j=0;j<=n;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;
  for (int i=n;i>=0;i--)
  {
    if(dp[n-1][i]!=bad)
    {
      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());
  return ans;
}

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