Submission #1258624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258624		allin27x	Festival (IOI25_festival)	C++20	0 / 100	133 ms	121256 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(); 
	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);
	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;
	}
	vector<signed> ans;
	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);
	}
	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