제출 #1254033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254033		fve5	Festival (IOI25_festival)	C++20	0 / 100	24 ms	4544 KiB

festival

#include <bits/stdc++.h>
#include "festival.h"
using namespace std;

typedef long long i64;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    array<vector<int>, 5> things;
    for (int i = 0; i < P.size(); i++)
        things[T[i]].push_back(P[i]);
    for (auto &x: things)
        sort(things.begin(), things.end());

    vector<i64> t1_ps = {0};
    for (auto x: things[1])
        t1_ps.push_back(t1_ps.back() + x);
    
    i64 rem = A;

    pair<int, int> best = {upper_bound(t1_ps.begin(), t1_ps.end(), A) - t1_ps.begin() - 1, 0};
    
    for (int i = 0; i < things[2].size(); i++) {
        A = (A - things[2][i]) * 2;
        if (A < 0) break;
        best = max(best, {i + 1 + upper_bound(t1_ps.begin(), t1_ps.end(), A) - t1_ps.begin() - 1, i + 1});
    }

    vector<int> ans;
    for (int i = 0; i < best.second; i++) ans.push_back(things[2][i]);
    while (ans.size() < best.first) ans.push_back(things[1][ans.size() - best.second]);
    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