제출 #1252474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252474		comgaTramAnh	Festival (IOI25_festival)	C++20	5 / 100	57 ms	6840 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) {
  std::vector <int> ret;
  std::vector <std::vector <std::pair <int, int>>> save(5);
  for (int i = 0; i < (int) T.size(); i++) {
    save[T[i]].push_back(std::make_pair(P[i], i)); 
  }  
  for (int i = 1; i <= 4; i++) {
    std::sort(save[i].begin(), save[i].end()); 
    std::reverse(save[i].begin(), save[i].end()); 
  }
  long long X = A; 
  while (true) {
    bool checkEmpty = true; 
    for (int i = 1; i <= 4; i++) {
      if (save[i].empty() == false) {
        checkEmpty = false; 
      }
    }
    if (checkEmpty == true) {
      break; 
    }
    long long maxi = -1; 
    int type = -1;
    int id = -1;  
    for (int i = 1; i <= 4; i++) {
      if (save[i].empty() == true) {
        continue; 
      }
      std::pair <int, int> element = save[i].back(); 
      if (X >= element.first) {
        if (maxi < (X - element.first) * i) {
          maxi = (X - element.first) * i;
          type = i;
          id = element.second; 
        }   
      }
    }
    if (type == -1) {
      break; 
    }
    save[type].pop_back(); 
    ret.push_back(id);
    X = maxi;  
  }
  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