제출 #1258611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258611		allin27x	축제 (IOI25_festival)	C++20	24 / 100	58 ms	12528 KiB

festival

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

const int INF = 3e15;

int tk;

struct coupon{
	int p, t, idx;
	void apply(){
		tk -= p; tk *= t;
		if (tk > INF) tk = INF;
		if (tk < 0) tk = -1;
	}
};

vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) {
	int n = P.size(); 
	vector<coupon> twos, ones;
	for (int i=0; i<n; i++) {
		if (T[i] == 2) twos.push_back({P[i], T[i], i});
		else ones.push_back({P[i], T[i], i});
	}
	sort(twos.begin(), twos.end(), [](coupon &a, coupon &b){return a.p < b.p;});
	sort(ones.begin(), ones.end(), [](coupon &a, coupon &b){return a.p < b.p;});
	vector<int> pr = {0};
	for (auto [p, t, idx]: ones) pr.push_back(pr.back() + p);
	tk = A;
	int mx = 0, m2 = 0;
	for (int i=0; i<twos.size(); i++){
		twos[i].apply();
		if (tk < 0) break;
		int l = 0, r = pr.size() - 1;
		while (l<r){
			int m = (l+r+1)/2;
			if (pr[m] <= tk) l = m; else r = m-1; 
		}
		if (i + 1 + l > mx) mx = i+1+l, m2 = i+1;
	}
	tk = A;
	vector<signed> ans;
	for (int i=0; i<m2; i++) ans.push_back(twos[i].idx), twos[i].apply();
	for (int i=0; i<ones.size(); i++) if (tk >= ones[i].p) ones[i].apply(), ans.push_back(ones[i].idx); else break;
	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