제출 #1261481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261481		avighna	Festival (IOI25_festival)	C++20	0 / 100	1093 ms	10812 KiB

festival

#include <bits/stdc++.h>

struct item {
  int64_t i, p, t;
};

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  const int n = P.size();
  std::vector<item> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = {i, P[i], T[i]};
  }
  std::sort(a.begin(), a.end(), [&](item i, item j) {
    if (i.t != j.t) {
      return i.t > j.t;
    }
    return i.p < j.p;
  });
  int _n = n;
  for (int i = 0; i < n; ++i) {
    if (a[i].t == 1) {
      _n = i;
      break;
    }
  }
  std::vector<int> ansl, ansr;
  int64_t max = 0;
  const int lg = 20;
  // for each n, fix how many chosen in left, right
  for (int i = 0; i <= std::min(lg, n); ++i) {
    int64_t vall = 0, valr = 0;
    std::vector<int> cur_ansl, cur_ansr;
    int ptr1 = 0, ptr2 = _n;
    for (int size = i; size <= n; ++size) {
      for (; ptr1 < i and ptr1 < _n; ++ptr1) {
        cur_ansl.push_back(ptr1);
        vall = a[ptr1].t * (vall - a[ptr1].p);
      }
      for (; ptr2 - _n < size - i and ptr2 < n; ++ptr2) {
        cur_ansr.push_back(ptr2);
        valr = a[ptr2].t * (valr - a[ptr2].p);
      }
      int64_t cur = (int64_t(A) << i) + (vall + valr);
      if (cur > 0 and cur_ansl.size() + cur_ansr.size() > max) {
        max = cur_ansl.size() + cur_ansr.size();
        ansl = cur_ansl, ansr = cur_ansr;
      }
    }
  }
  std::vector<int> ans;
  for (int &i : ansl) {
    ans.push_back(i);
  }
  for (int &i : ansr) {
    ans.push_back(i);
  }
  return ans;
}

• 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