제출 #1251538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251538		windowwife	축제 (IOI25_festival)	C++20	100 / 100	112 ms	102840 KiB

festival

#ifndef rtgsp
#include "festival.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 2e5 + 2, LG = 40;
const ll inf = 1e18;
int n, cnt, p[maxn], t[maxn], track[maxn][LG], res, opt;
bool state;
ll a, ps[maxn], dp[maxn][LG];
vector<int> t1, t2, ans, ans2;

bool cmp1 (int x, int y)
{
    return p[x] < p[y];
}
bool cmp2 (int x, int y)
{
    return 1LL*p[x]*t[x]*(t[y] - 1) < 1LL*p[y]*t[y]*(t[x] - 1);
}
bool maximize (ll &a, ll b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T)
{
    n = P.size(); a = A; cnt = 0; res = 0; opt = 0;
    t1.clear(); t2.clear(); ans.clear(); ans2.clear();
    state = false;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < LG; j++)
            dp[i][j] = -inf;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < LG; j++)
            track[i][j] = -1;
    for (int i = 0; i < n; i++)
    {
        p[i] = P[i];
        t[i] = T[i];
        if (t[i] == 1) t1.push_back(i);
        else t2.push_back(i);
    }
    sort(t1.begin(), t1.end(), cmp1);
    for (int i = 0; i < (int)t1.size(); i++)
        ps[i + 1] = ps[i] + p[t1[i]];
    sort(t2.begin(), t2.end(), cmp2);
    for (int i : t2)
    {
        if (state == false && a > min((a - p[i])*t[i], inf))
        {
            state = true;
            dp[0][0] = a;
        }
        if (state)
        {
            cnt++;
            for (int j = 0; j < min(LG - 1, cnt); j++)
            {
                if (maximize(dp[cnt][j], dp[cnt - 1][j])) track[cnt][j] = -1;
                if (dp[cnt - 1][j] >= p[i] && maximize(dp[cnt][j + 1], (dp[cnt - 1][j] - p[i])*t[i])) track[cnt][j + 1] = i;
            }
        }
        else
        {
            a = min((a - p[i])*t[i], inf);
            ans.push_back(i);
        }
    }
    if (cnt == 0) dp[0][0] = a;
    for (int j = 0; j <= min(LG - 1, cnt); j++)
    {
        if (dp[cnt][j] == -inf) break;
        int ok = j + upper_bound(ps, ps + (int)t1.size(), dp[cnt][j]) - ps - 1;
        if (res < ok)
        {
            res = ok;
            opt = j;
        }
    }
    int i = cnt, j = opt;
    while (i > 0)
    {
        if (track[i][j] != -1)
        {
            ans2.push_back(track[i][j]);
            j--;
        }
        i--;
    }
    reverse(ans2.begin(), ans2.end());
    for (int i : ans2) ans.push_back(i);
    for (int i : t1)
    {
        if (dp[cnt][opt] >= p[i])
        {
            ans.push_back(i);
            dp[cnt][opt] -= p[i];
        }
    }
    return ans;
}

#ifdef rtgsp
int main()
{
    freopen(task".in", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int N, A;
    vector<int> P, T;
    cin >> s >> N >> A;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        P.push_back(x);
        T.push_back(y);
    }
    vector<int> ans = max_coupons(A, P, T);
    cout << ans.size();
}
#endif // rtgsp

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