Submission #1252744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252744		comgaTramAnh	Festival (IOI25_festival)	C++20	5 / 100	63 ms	26044 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]; 
  };
  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::sort(ones.begin(), ones.end(), compareOne); 
  std::sort(other.begin(), other.end(), compare); 
  std::cout << std::endl;
  int n = (int) ones.size(); 
  int numbT = std::min(90, (int) other.size());
  const long long inf = -1; 
  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) A;             
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= numbT; j++) {
      if (f[i][j] == inf) {
        continue; 
      }
      if (i < n && f[i][j] >= P[ones[i]]) {
        if (f[i + 1][j] < f[i][j] - P[ones[i]]) {
          f[i + 1][j] = f[i][j] - P[ones[i]];
          trace[i + 1][j] = std::make_pair(i, j); 
        } 
      }
      if (j < numbT && f[i][j] >= P[other[j]]) {
        if (f[i][j + 1] < (long long) (f[i][j] - P[other[j]]) * T[other[j]]) {
          f[i][j + 1] = (long long) (f[i][j] - P[other[j]]) * T[other[j]];
          trace[i][j + 1] = std::make_pair(i, j);  
        } 
      }    
    }
  }
  std::vector <int> ret;
  int maxNumb = -1; 
  int posi = -1, posj = -1; 
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= numbT; j++) {
      if (maxNumb < i + j && f[i][j] != inf) {
        maxNumb = i + j;
        posi = i;
        posj = j; 
      }
    }
  }                                      
  while (posi > 0 || posj > 0) {
    std::pair <int, int> prev = trace[posi][posj];                 
    if (prev.second == posj) {
      ret.push_back(ones[prev.first]); 
      posi = prev.first; 
    }
    else {
      ret.push_back(other[prev.second]); 
      posi = prev.first; 
      posj = prev.second; 
    }
  }
  std::reverse(ret.begin(), ret.end()); 
  return ret;  
}

• 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