제출 #1261012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261012		gelastropod	축제 (IOI25_festival)	C++20	0 / 100	1196 ms	2162688 KiB

festival

#include "festival.h"

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

bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
	return a.second.first * a.second.second * b.second.second + b.second.first * b.second.second <
		b.second.first * a.second.second * b.second.second + a.second.first * a.second.second;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
	vector<pair<int, pair<int, int>>> vals;
	for (int i = 0; i < P.size(); i++) {
		vals.push_back({ i, { P[i], T[i] } });
	}
	sort(vals.begin(), vals.end(), comp);
	vector<pair<int, int>> aa(P.size() + 1, { -1, -1 });
	vector<vector<int>> p(P.size(), vector<int>(P.size(), -1));
	aa[0] = { A, -1 };
	for (int i = 0; i < P.size(); i++) {
		for (int j = P.size() - 1; j >= 0; j--) {
			if (aa[j].first < vals[i].second.first) continue;
			if (aa[j + 1].first < (aa[j].first - vals[i].second.first) * vals[i].second.second) {
				aa[j + 1] = { (aa[j].first - vals[i].second.first) * vals[i].second.second, i};
				p[j][i] = aa[j].second;
			}
		}
	}
	int maxC = 0;
	for (maxC = P.size(); maxC >= 0; maxC--) {
		if (aa[maxC].first >= 0) break;
	}
	vector<int> res;
	int crnt = aa[maxC].second;
	while (crnt != -1) {
		maxC--;
		res.push_back(crnt);
		crnt = p[maxC][crnt];
	}
	reverse(res.begin(), res.end());
	for (int i = 0; i < res.size(); i++) res[i] = vals[res[i]].first;
	return res;
}

• 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