Submission #1263098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263098		Itamar	Festival (IOI25_festival)	C++20	0 / 100	46 ms	6712 KiB

festival

#include "festival.h"
#include <cassert>
#include <cstdio>

#include "festival.h"
using namespace std;
#include<algorithm>
#define ll long long
#define vll vector<ll>

int n;


std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  vector<int> ind;
  n = P.size();
  for(int i = 0; i < n; i++)ind.push_back(i);
  auto val = [&](int i, ll x){
    return max((ll)-1,(x-P[i])*T[i]);

  };
  sort(ind.begin(), ind.end(), [&](int i, int j){
    return val(i,val(j,0)) < val(j,val(i,0));
  });
  ll cur = A;
  vector<int> ans;
  int i = 0;
  for(; i < n; i++){
    if(val(ind[i],cur) >= cur){
      ans.push_back(ind[i]);
      cur = val(ind[i],cur);
      if(cur > 1e15){
        for(int j = i+1; j < n; j++)ans.push_back(ind[j]);
        return ans;
      }
    }else break;
  }
  vector<int> his[5];
  for(; i < n; i++){
    if(T[ind[i]] == 1 || his[T[ind[i]]].size() <= 30)his[T[ind[i]]].push_back(ind[i]);
  }
  sort(his[1].begin(), his[1].end(), [&](int i, int j){
    return P[i] < P[j];
  });
  vll s(his[1].size()+1, 0);
  for(int i = 0; i < his[1].size(); i++)s[i+1] = s[i]+P[his[1][i]];

  vll maxi = {0,0,0,0};
  for(int i = 0; i < his[2].size(); i++){
    for(int j = 0; j < his[3].size(); j++){
      for(int k = 0; k < his[4].size(); k++){
        ll curcur = cur;
        for(int t = 0; t <= i; t++)curcur = val(his[2][t], curcur);
        for(int t = 0; t <= j; t++)curcur = val(his[3][t], curcur);
        for(int t = 0; t <= k; t++)curcur = val(his[4][t], curcur);
        if(curcur < 0)continue;
        int pos = upper_bound(s.begin(), s.end(), curcur)-s.begin()-1;
        if(pos+i+j+k+3 > maxi[0]+maxi[1]+maxi[2]+maxi[3]){
          maxi = {pos, i, j, k};
        }
      }
    }
  }
  for(int i = 0; i < maxi[0]; i++)ans.push_back(his[1][i]);
  for(int i = 0; i < maxi[1]; i++)ans.push_back(his[2][i]);
  for(int i = 0; i < maxi[2]; i++)ans.push_back(his[3][i]);
  for(int i = 0; i < maxi[3]; i++)ans.push_back(his[4][i]);
  return ans;
}

/*
int main() {
  int N, A;
  assert(2 == scanf("%d %d", &N, &A));
  std::vector<int> P(N), T(N);
  for (int i = 0; i < N; i++)
    assert(2 == scanf("%d %d", &P[i], &T[i]));
  fclose(stdin);

  std::vector<int> R = max_coupons(A, P, T);

  int S = R.size();
  printf("%d\n", S);
  for (int i = 0; i < S; i++)
    printf("%s%d", (i == 0 ? "" : " "), R[i]);
  printf("\n");
  fclose(stdout);

  return 0;
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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