Submission #1267250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267250		nerrrmin	Festival (IOI25_festival)	C++20	24 / 100	63 ms	12532 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
long long n, a;

struct coupon
{
    long long cost, type, index;
    coupon(){};
    coupon(long long _cost, long long _type, long long _index)
    {
        cost = _cost;
        type = _type;
        index = _index;
    }
};
bool cmp(coupon c1, coupon c2)
{
    return (c1.cost < c2.cost);
}
vector < coupon > g[5];
vector < long long > sums;
long long dp[maxn];

long long getone(long long tokens)
{
    long long l = 0, r = sums.size()-1, mid = 0, ans = 0;
    while(l <= r)
    {
        mid = (l + r)/2;
        if(sums[mid] <= tokens)
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;

    }
    return ans;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    a = A;
    n = P.size();

    for (long long i = 0; i < n; ++ i)
    {
        g[T[i]].pb(coupon(P[i], T[i], i));
    }
    for (long long curr = 1; curr <= 4; ++ curr)
        sort(g[curr].begin(), g[curr].end(), cmp);
    sums.pb(0);
    long long pre = 0;
    for (auto &[c, t, i]: g[1])
    {
        pre += c;
       sums.pb(pre);
    }
    vector < int > res;

    long long tokens = a;
    dp[0] = getone(tokens);

    long long mx = 0, best = dp[0];
    long long cnt = 0;
    for (auto &[c, t, i]: g[2])
    {
        if(tokens < c)break;
        cnt ++;
        tokens -= c;
        if(tokens < 1LL * 1e17)tokens *= 2;

      ///  cout << "@ " << cnt << " " << i << endl;
      ///  cout << tokens << " for the ones " << endl;
        dp[cnt] = cnt + getone(tokens);
        if(best < dp[cnt])
        {
            best = dp[cnt];
            mx = cnt;
        }
    }
   /// for (long long i = 0; i <= g[2].size(); ++ i)
   ///     cout << dp[i] << " ";
  ///  cout << endl;
  ///  cout << mx << " " << best << endl;
    for (long long i = 1; i <= mx; ++ i)
        res.pb(g[2][i-1].index);
    for (long long i = 1; i <= best - mx; ++ i)
        res.pb(g[1][i-1].index);
  return res;
}

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