제출 #1269570

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

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;
const ll INF = 200005000000009;

struct ban
{
    int i;
    ll p, t;
};
ll F(ll A, const ban& u)
{
    return (A - u.p) * u.t;
}
bool operator<(const ban& a, const ban& b)
{
    return F(F(0, a), b) < F(F(0, b), a);
}

std::vector<int> max_coupons(int aa, std::vector<int> P, std::vector<int> T)
{
    int n;
    n = sz(P);

    vector<pair<ll, ban> > v;
    for (int i = 0; i < n; ++i)
    {
        ban u;
        u.p = P[i];
        u.t = T[i];
        u.i = i;
        if (u.t == 1)
            v.push_back(m_p(INF, u));
        else
        {
            ll x = u.p * u.t;
            if (x % (u.t - 1) == 0)
                x /= (u.t - 1);
            else
            {
                x /= (u.t - 1);
                ++x;
            }
            v.push_back(m_p(x, u));
        }
    }
    sort(all(v));
    reverse(all(v));

    priority_queue<ban> q;
    ll A = aa;
    vector<int> ans;
    while (1)
    {
        while (!v.empty() && A >= v.back().fi)
        {
            q.push(v.back().se);
            v.pop_back();
        }
        if (q.empty())
            break;
        ban u = q.top();
        q.pop();
        A = min(INF, (A - u.p) * u.t);
        ans.push_back(u.i);
    }

    for (int i = 0; i < sz(v); ++i)
        v[i].fi = 0;
    sort(all(v));
    reverse(all(v));

    vector<vector<ll> > dp(sz(v) + 1, vector<ll>(sz(v), -1));
    dp[0][0] = A;
    for (int i = 0; i < sz(v); ++i)
    {
        ban u = v[i].se;
        for (int q = 0; q <= i; ++q)
        {
            dp[i + 1][q] = max(dp[i + 1][q], dp[i][q]);
            if (dp[i][q] >= u.p)
                dp[i + 1][q + 1] = max(dp[i + 1][q + 1], (dp[i][q] - u.p) * u.t);
        }
    }

    vector<int> yans;
    for (int q = sz(v); q >= 0; --q)
    {
        if (dp[sz(v)][q] >= 0)
        {
            for (int i = sz(v) - 1; i >= 0; --i)
            {
                if (dp[i + 1][q] == dp[i][q])
                    continue;
                yans.push_back(v[i].se.i);
                --q;
            }
        }
    }
    reverse(all(yans));
    for (int i = 0; i < sz(yans); ++i)
        ans.push_back(yans[i]);
    return ans;
}

/*
4 13
4 1
500 3
8 3
14 4

2 1000
999 4
3 1
*/

• 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