Submission #1283389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283389		janson0109	축제 (IOI25_festival)	C++20	51 / 100	98 ms	82220 KiB

festival

#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 1000000007;

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    vector<pair<ll,ll>> srt;
    vector<pair<ll,ll>> t1;
    ll n = P.size();
    for(ll i=0; i<n; i++) {
        if(T[i] == 1) {
            t1.push_back(make_pair(P[i], i));
        } else {
            ll x = 6 * T[i] / (T[i] - 1);
            x *= P[i];
            srt.push_back(make_pair(x, i));
        }
    }
    sort(srt.begin(), srt.end()); sort(t1.begin(), t1.end());
    vector<pair<ll,ll>> srt2;
    vector<int> R; vector<bool> used(n,0);
    ll B = A;
    for(ll i=0; i<srt.size(); i++) {
        if((B - P[srt[i].S]) * T[srt[i].S] >= B) {
            R.push_back(srt[i].S);
            used[srt[i].S] = 1;
            B = (B - P[srt[i].S]) * T[srt[i].S];
            if(B >= 1e18) {
                for(ll i=0; i<n; i++) if(!used[i]) R.push_back(i);
                return R;
            }
        } else srt2.push_back(srt[i]);
    }
    ll m = srt2.size();
    vector<vector<pair<ll,ll>>> dp(m+1, vector<pair<ll,ll>>(67, make_pair(-1,-1)));
    dp[0][0].F = B;
    for(ll i=0; i<m; i++) for(ll j=0; j<67; j++) {
        dp[i+1][j] = dp[i][j];
        if(j > 0 && (dp[i][j-1].F - P[srt2[i].S]) * T[srt2[i].S] > dp[i+1][j].F) dp[i+1][j] = make_pair((dp[i][j-1].F - P[srt2[i].S]) * T[srt2[i].S], i);
    }

    vector<ll> smt1 = {0};
    for(ll i=0; i<t1.size(); i++) smt1.push_back(smt1.back() + t1[i].F);
    
    pair<ll,pair<ll,ll>> opt = make_pair(-1, make_pair(0,0));
    for(ll i=0; i<67; i++) {
        if(dp.back()[i].F < 0) continue;
        ll get = i - 1 + (upper_bound(smt1.begin(), smt1.end(), dp.back()[i].F) - smt1.begin());
        if(get > opt.F) opt = make_pair(get, make_pair(i, get - i));
    }
    ll cur1 = m, cur2 = opt.S.F;
    while(cur2 != 0) {
        cur1 = dp[cur1][cur2].S;
        cur2--;
        R.push_back(srt2[cur1].S);
    }
    for(ll i=0; i<opt.S.S; i++) R.push_back(t1[i].S);
    return R;

}

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