제출 #1280732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280732		tschav_	축제 (IOI25_festival)	C++20	5 / 100	65 ms	9580 KiB

festival

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

using ll = long long;

vector<int> max_coupons(int A, vector<int> P, vector<int> T){
	int sum = accumulate(T.begin(),T.end(),0);
	int n = P.size();

	if(sum != n){
		vector<int> R;
		
		using pii = pair<int,int>;
		
		priority_queue<pii> pq[5];
		
		for(int i = 0; i < n; ++i){
			pq[T[i]].push(pii{-P[i] * T[i], i});
		}
		ll curr = A;
		while(R.size() < n){
		    int mx = 0;
		    int mxc = 0;
		    for(int i = 1; i <= 4; ++i){
		        if(pq[i].empty()) continue;
		        int H = pq[i].top().second;
		        int pay = pq[i].top().first;
		        if(curr * T[H] + pay >= mx) {
		            mxc = i;
		            mx = curr * T[H] + pay;
		        }
		    }
		    if(mxc == 0) break;
		    auto [t,ind] = pq[mxc].top();
		    pq[mxc].pop();
		    curr = (curr - P[ind]) * T[ind];
		    R.push_back(ind);
		}
		
		return R;
	}
	
	
	vector<int> R;
	
	vector<int> idx(n);
	iota(idx.begin(),idx.end(),0);
	
	sort(idx.begin(),idx.end(),[&](int i, int j) {
		return P[i] < P[j];
	});
	
	int cnt = 0;
	int curr= A;
	for(int i = 0; i < n; ++i){
		if(curr >= P[idx[i]]){
			++cnt;
			R.push_back(idx[i]);
			curr -= P[idx[i]];
		} else break;
	}
	
	return R;
}

• 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