제출 #1254041

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

festival

#pragma GCC optimize("trapv")
#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) {
    i64 sum = 0;
    array<vector<pair<int, int>>, 5> things;
    for (int i = 0; i < P.size(); i++) {
        things[T[i]].push_back({P[i], i});
        sum += P[i];
    }
    for (auto &x: things)
        sort(x.begin(), x.end());

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

    pair<int, int> best = {upper_bound(t1_ps.begin(), t1_ps.end(), rem) - t1_ps.begin() - 1, 0};
    
    for (int i = 0; i < things[2].size(); i++) {
        rem = (rem - things[2][i].first) * 2;
        if (rem >= sum) {
            vector<int> ans;
            for (auto x: things[2]) ans.push_back(x.second);
            for (auto x: things[1]) ans.push_back(x.second);
            return ans;
        }
        if (rem < 0) break;
        best = max(best, {i + 1 + upper_bound(t1_ps.begin(), t1_ps.end(), rem) - t1_ps.begin() - 1, i + 1});
    }

    vector<int> ans;
    for (int i = 0; i < best.second; i++) ans.push_back(things[2][i].second);
    while (ans.size() < best.first) ans.push_back(things[1][ans.size() - best.second].second);
    return ans; 
}

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