제출 #1258627

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

festival

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

const int INF = 3e15;
const int N = 2e5+4;
const int ANS = 70;


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

bool comp(coupon &a, coupon &b){
	if (a.t == 1 && b.t == 1) return a.p < b.p;
	return a.p * a.t * (b.t - 1) < b.p * b.t * (a.t - 1);
}

int dp[N][ANS];
int us[N][ANS];

vector<signed> max_coupons(signed a, vector<signed> P, vector<signed> T) {
	int n = P.size(); int A = a;
	vector<signed> prans;
	vector<signed> ans;
	vector<coupon> cp, ones;
	for (int i=0; i<n; i++){
		if (T[i] == 1) ones.push_back({P[i], T[i], i});
		else cp.push_back({P[i], T[i], i});
	}
	sort(cp.begin(), cp.end(), comp);
	sort(ones.begin(), ones.end(), comp);
	reverse(cp.begin(), cp.end());
	while (1){
		if (cp.empty()) break;
		coupon cn = cp.back();
		if (cn.apply(A) < A) break;
		prans.push_back(cn.idx); A = cn.apply(A);
		cp.pop_back();
	}
	reverse(cp.begin(), cp.end());
	vector<int> pr = {0};
	for (auto [p, t, idx]: ones) pr.push_back(pr.back() + p);
	for (int i=0; i<N; i++) for (int j=0; j<ANS; j++) dp[i][j] = -1;
	dp[0][0] = A; 
	for (int i=1; i<=cp.size(); i++){
		coupon cn = cp[i-1];
		for (int j=0; j<ANS; j++) dp[i][j] = dp[i-1][j];

		for (int j=1; j<ANS; j++) {
			if (dp[i][j] > cn.apply(dp[i-1][j-1])) continue;
			dp[i][j] = cn.apply(dp[i-1][j-1]);
			us[i][j] = 1;
		}
	}
	int mx = 0, mt = 0;
	for (int i=0; i<ANS; i++){
		int l = 0, r = pr.size() - 1;
		if (dp[cp.size()][i] < 0) continue;
		while (l<r){
			int m = (l+r+1)/2;
			if (pr[m] <= dp[cp.size()][i]) l = m; else r = m-1; 
		}
		if (i + l > mx) mx = i+l, mt = i;
	}
	int i = cp.size(); int m = mt; int left = dp[i][mt];
	while (i){
		if (!us[i][m]) {i--; continue;}
		i--; m--;
		ans.push_back(cp[i].idx);
	}
	reverse(ans.begin(), ans.end());
	for (int i=0; i<ones.size(); i++) {
		if (left < ones[i].p) break;
		left = ones[i].apply(left);
		ans.push_back(ones[i].idx);
	}
	vector<signed> finans;
	for (int x: prans) finans.push_back(x);
	for (int x: ans) finans.push_back(x);
	return finans;
}

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