| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1253689 | bynix | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
using namespace std;
#include "festival.h"
typedef long long ll;
const ll lim = 1e18;
vector<ll> max_coupons(ll A, vector<ll> P, vector<ll> T) {
ll N = P.size();
vector<ll> t1, t, temp, pre1(N+1, lim*2), R;
for (ll i = 0; i < N; i++){
if (T[i] == 1) t1.push_back(i);
else temp.push_back(i);
}
ll t1s = t1.size(), ts = temp.size();
sort(t1.begin(), t1.end(), [&](ll& a, ll& b){ return P[a] < P[b]; });
sort(temp.begin(), temp.end(), [&](ll& a, ll& b){
ll l = T[a]*((T[b]*P[b]) + P[a]), r = T[b]*((T[a]*P[a]) + P[b]);
return l > r;
});
ll i = 1;
ll prev = (A - P[temp[0]]) * T[temp[0]], cur, M = A;
if (prev > 0){
for (; i < ts; i++){
cur = (prev - P[temp[i]])*T[temp[i]];
if (cur < prev) break;
cur = min(cur, lim);
prev = cur;
}
if (i == ts - 1 && prev < cur) i++;
for (ll j = 0; j < i; j++) R.push_back(temp[j]);
M = prev;
} else i = 0;
map<ll, ll> f;
for (; i < ts; i++){
f[T[temp[i]]]++;
if (f[T[temp[i]]] <= 32) t.push_back(temp[i]);
}
ts = t.size();
vector<vector<ll>> dp(ts + 1, vector<ll>(ts + 1, -1)), log(ts + 1, vector<ll>(ts + 1, -1));
dp[0][0] = M;
for (ll i = 1; i <= ts; i++){
for (ll j = 0; j < i; j++){
dp[i][j] = dp[i - 1][j];
if (dp[i][j] < 0) break;
dp[i][j] = min(dp[i][j], lim);
}
for (ll j = 1; j <= i; j++){
ll val = (dp[i - 1][j - 1] - P[t[i-1]])*T[t[i-1]];
if (val >= dp[i][j]){
dp[i][j] = val;
log[i][j] = j;
}
if (dp[i][j] < 0) break;
dp[i][j] = min(dp[i][j], lim);
}
}
pre1[0] = 0;
for (ll i = 0; i < t1s; i++)
pre1[i + 1] = pre1[i] + P[t1[i]], pre1[i + 1] = min(pre1[i + 1], lim);
ll mc = 0ll, mt1 = 0ll, mt = 0ll, ct1 = 0ll;
for (ll i = 0; i <= ts; i++){
if (dp[ts][i] < 0) break;
ll pos = upper_bound(pre1.begin(), pre1.end(), dp[ts][i]) - pre1.begin();
if (pos == 0) ct1 = 0;
else ct1 = min(pos - 1, t1s);
if (ct1 + i > mc) mc = ct1 + i, mt1 = ct1, mt = i;
}
cur = mt;
ll c = ts, b = 0;
vector<ll> R2;
while (b < mt){
if (log[c][cur] >= 0){
R2.push_back(t[c-1]);
b++;
}
cur = mt - b, c--;
}
reverse(R2.begin(), R2.end());
for (auto &e: R2) R.push_back(e);
for (ll i = 0; i < mt1; i++) R.push_back(t1[i]);
return R;
}