제출 #1252433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252433		NekoRolly	축제 (IOI25_festival)	C++20	5 / 100	1094 ms	12468 KiB

festival

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

typedef long long ll;
typedef pair<ll,ll> pll;

struct coupon{
    ll p,t,id;
};

bool comp(coupon A,coupon B){ // *{P[i], T[i]}
    auto [p, a, ida] = A;
    auto [q, b, idb] = B;
    if (a == b) return p <= q;
    if (a == 1 || b == 1) return b == 1;
    return a*b*p + b*q <= a*b*q + a*p;
}

vector<int> max_coupons(int _A,vector<int> P,vector<int> T){
    int n = P.size(), max_t = 0;
    ll A = _A;
    coupon a[n];

    for (int i=0; i<n; i++){
        a[i] = {P[i], T[i], i};
        max_t = max(max_t, T[i]);
    }

    sort(a, a+n, comp);
    vector<int> vans;

    if (max_t <= 0){
        int ini = 0;
        while (ini < n && a[ini].t == 2) ini++;

        int best_i = -1, ans = 0;
        int m = n-ini+1;
        ll pr[m];
        pr[0] = 0;
        for (int i=ini; i<n; i++){
            pr[i-ini+1] = pr[i-ini] + a[i].p;
            if (pr[i-ini+1] <= A) ans = i-ini+1;
        }

        ll aux = A;
        for (int i=0; i<ini; i++){
            // cout << a[i].p << " " << a[i].t << " " << a[i].id << "\n";
            if (A < a[i].p) break;
            A = 2*(A - a[i].p);
            int r = upper_bound(pr, pr+m, A) - pr;
            int val = (i+1) + (r-1);
            if (ans < val) ans = val, best_i = i;
        }
        A = aux;
        // cout << "best_i : " << best_i << "\n";
        // cout << "ans : " << ans << "\n";

        for (int i=0; i<=best_i; i++){
            A = 2*(A - a[i].p);
            vans.push_back(a[i].id);
        }

        for (int i=ini; i<n; i++){
            if (A < a[i].p) break;
            A -= a[i].p;
            vans.push_back(a[i].id);
        }

        return vans;
    }
    else if (max_t <= 2){
        vector<pll> v2,v1;

        for (int i=0; i<n; i++){
            if (a[i].t == 1) v1.push_back({a[i].p, a[i].id});
            else v2.push_back({a[i].p, a[i].id});
        }

        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end());

        ll aux = A;
        int ans = 0, best = 0;
        for (int l=0; l<=v2.size(); l++){
            int val = l;
            A = aux;
            for (int i=0; i<l; i++)
                A = 2*(A - v2[i].first);
            if (A < 0) continue;
            for (int i=0; i<v1.size(); i++){
                if (A < v1[i].first) break;
                A -= v1[i].first;
                val++;
            }
            if (ans < val){
                ans = val;
                best = l;
            }
        }

        for (int i=0; i<best; i++)
            vans.push_back(v2[i].second);
        for (int i=0; i<ans-best; i++)
            vans.push_back(v1[i].second);

        return vans;
    }

    for (int i=0; i<n; i++)
        vans.push_back(a[i].id);

    return vans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 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