제출 #1263120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263120		Itamar	축제 (IOI25_festival)	C++20	100 / 100	91 ms	7992 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 (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};
  vector<int> add;
  for( 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;
        vector<int> v;
        for(int t = 0; t < i; t++)v.push_back(his[2][t]);
        for(int t = 0; t < j; t++)v.push_back(his[3][t]);
        for(int t = 0; t < k; t++)v.push_back(his[4][t]);
        sort(v.begin(), v.end(), [&](int i, int j){
          return val(i,val(j,cur)) < val(j,val(i,cur));
        });
        for(auto x : v){
          curcur = val(x, curcur);
          if(curcur < 0)break;
        }
        if(curcur < 0)continue;
        int pos = upper_bound(s.begin(), s.end(), curcur)-s.begin()-1;
        if(pos+i+j+k > maxi[0]+maxi[1]+maxi[2]+maxi[3]){
          maxi = {pos, i, j, k};
          add = v;
        }
      }
    }
  }
  for(int a : add)ans.push_back(a);
  for( i = 0; i < maxi[0]; i++)ans.push_back(his[1][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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18