제출 #1252888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252888		comgaTramAnh	축제 (IOI25_festival)	C++20	51 / 100	81 ms	44220 KiB

festival

#include <bits/stdc++.h> 
//#include "festival.h"

using namespace std;
std::vector <int> max_coupons(int A, std::vector <int> P, std::vector <int> T) {
  auto compare = [&](int i, int j) {
    std::pair <int, int> a = std::make_pair(P[i], T[i]); 
    std::pair <int, int> b = std::make_pair(P[j], T[j]); 
    return (1LL * a.first * a.second * b.second + 1LL * b.first * b.second < 1LL * b.first * a.second * b.second + 1LL * a.first * a.second);
  };
  auto compareOne = [&](int i, int j) {
    return P[i] < P[j]; 
  };
  const long long inf = 10000000000000007LL;
  std::vector <int> ones, other;
  for (int i = 0; i < (int) T.size(); i++) {
    if (T[i] == 1) {
      ones.push_back(i); 
    }
    else {
      other.push_back(i); 
    }
  } 
  std::vector <int> ret; 
  std::sort(ones.begin(), ones.end(), compareOne); 
  std::sort(other.begin(), other.end(), compare);
  long long X = A;
  bool ok = false; 
  for (int i = 0; i < (int) other.size(); i++) {
    long long nextX = (long long) (X - P[other[i]]) * T[other[i]];
    if (nextX < X) {     
      ok = true;
      ret = std::vector <int>(other.begin(), other.begin() + i);                     
      other.erase(other.begin(), other.begin() + i); 
      break;    
    }
    else {
      X = nextX; 
    }
    if (X >= inf) {      
      ret = other; 
      for (int i = 0; i < (int) ones.size(); i++) {
        ret.push_back(ones[i]); 
      }
      return ret; 
    }
  } 
  if (ok == false) {   
    ret = other; 
    other.clear(); 
  } 
  int n = (int) other.size(); 
  int numbT = std::min(32, (int) other.size());
  std::vector <std::vector <std::pair <int, int>>> trace(n + 1); 
  std::vector <std::vector <long long>> f(n + 1);
  for (int i = 0; i <= n; i++) {
    f[i].resize(numbT + 1, -inf); 
    trace[i].resize(numbT + 1, std::make_pair(-1, -1)); 
  }        
  f[0][0] = (long long) X;             
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= numbT; j++) {
      if (f[i][j] == -inf) {
        continue; 
      }
      if (f[i + 1][j] < f[i][j]) {
        f[i + 1][j] = f[i][j];
        trace[i + 1][j] = std::make_pair(i, j); 
      }   
      if (j < numbT && f[i][j] >= P[other[j]]) {
        long long next_f = std::min(inf, (long long) (f[i][j] - P[other[j]]) * T[other[j]]);
        if (f[i + 1][j + 1] < next_f) {
          f[i + 1][j + 1] = next_f; 
          trace[i + 1][j + 1] = std::make_pair(i, j); 
        } 
      }
    }
  }
  std::vector <long long> sum((int) ones.size() + 1, 0LL);
  for (int i = 1; i <= (int) ones.size(); i++) {
    sum[i] = sum[i - 1] + P[ones[i - 1]]; 
  } 
  int posj = -1; 
  int maxNumb = -1; 
  int posOne = -1; 
  for (int j = 0; j <= numbT; j++) {
    long long X = f[n][j];
    if (X == -inf) {
      continue; 
    }
    int numbOnes = -1; 
    int lo = 0; 
    int hi = (int) ones.size(); 
    while (lo <= hi) {
      int mid = (lo + hi) / 2; 
      if (X >= sum[mid]) {
        numbOnes = mid; 
        lo = mid + 1; 
      }
      else {
        hi = mid - 1; 
      }
    }
    if (numbOnes != -1 && maxNumb < j + numbOnes) {
      maxNumb = j + numbOnes; 
      posj = j; 
      posOne = numbOnes;
    }
  }
  std::vector <int> tmp; 
  int i = n; 
  while (i > 0) {
    std::pair <int, int> prev = trace[i][posj];
    if (prev.second != posj) {                     
      tmp.push_back(other[prev.second]); 
      posj = prev.second; 
    } 
    i = prev.first; 
  }
  std::reverse(tmp.begin(), tmp.end());
  for (int i = 0; i < (int) tmp.size(); i++) {
    ret.push_back(tmp[i]);
  }
  long long V = f[n][posj];                                              
  for (int i = 0; i < (int) ones.size(); i++) {
    if (V >= P[ones[i]]) {
      V -= P[ones[i]];
      ret.push_back(ones[i]);
    } 
  } 
  return ret;  
}

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