Submission #1312494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312494		Dedibeat	Festival (IOI25_festival)	C++20	5 / 100	48 ms	7536 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()
ll safe_mul(ll x, ll y)
{
  if(x * y > 1e17) return 1e17;
  return x * y;
}
std::vector<int> max_coupons(int aa, std::vector<int> P, std::vector<int> T) {
  ll A = aa;
  int n = T.size();
  vector<int> one, two;
  for(int i = 0; i < n; i++)
  {
    if(T[i] == 1) one.push_back(i);
    else two.push_back(i);
  }
  sort(all(one), [&](int i, int j)
  {
    return P[i] < P[j];
  });
  sort(all(two), [&](int i, int j)
  {
    return P[i] < P[j];
  });


  vector<ll> pref((int)one.size());
  ll sum = 0;
  for(int i = 0; i < one.size(); i++) 
  {
    sum += P[one[i]];
    pref[i] = sum;
  }
  pref.push_back(1e18);


  int x = lower_bound(all(pref), A + 1) - pref.begin();
  int y = 0;
  int mx = x;
  for(int i = 0; i < two.size(); i++)
  {
    if(A < P[two[i]]) break;
    A = safe_mul(A - P[two[i]], 2);
    int j = lower_bound(all(pref), A + 1) - pref.begin();
    int tot = (i + 1 + j);
    if(tot > mx) 
    {
      x = j;
      y = i + 1;
    }
  }

  vector<int> ans;
  for(int i = 0; i < y; i++) ans.push_back(two[i]);
  for(int i = 0; i < x; i++) ans.push_back(one[i]);
  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: 0 / 16
• Subtask 7: 0 / 18