Submission #1283006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283006		nika7878	Festival (IOI25_festival)	C++20	51 / 100	77 ms	9780 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
#define ll long long

using namespace std;
const ll INF = 1e18;

vector<int> cur, best;
int best1;

void solve(int pos, ll tok, int type, vector<int> &a, vector<pair<ll, int> > &b, vector<int> &p, vector<int> &t) {

    if(type==1 || pos==a.size()) 
    {
        auto it=lower_bound(b.begin(), b.end(), make_pair(tok+1, -1))-b.begin();
        if (it+cur.size()>best.size()+best1) 
        {
            best=cur;
            best1=it;
        }
        return ;
    }
    if(tok>=p[a[pos]] && type>=t[a[pos]]) {
        cur.push_back(a[pos]);
        solve(pos+1, min((tok-p[a[pos]])*t[a[pos]], INF), type, a, b, p, t);
        cur.pop_back();
    }
    solve(pos + 1, tok, min(type, t[a[pos]] - 1), a, b, p, t);
}

vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
    vector<int> a;
    vector<pair<ll, int>> b;
    int n=p.size();
    for(int i=0; i<n; i++)
        t[i]!=1 ? a.push_back(i) : b.push_back({p[i], i});

    sort(a.begin(), a.end(), [&](int i, int j) 
    {
        if(t[i]==t[j]) 
            return p[i]<p[j];
        else
            return p[i]*t[i]*(t[j]-1) < p[j]*t[j]*(t[i]-1);
    });
    sort(b.begin(), b.end());

    for(int i=1; i<b.size(); i++)
        b[i].first+=b[i-1].first;

    vector<int> res;
    ll tok = A;

    for(auto i: a) 
    {
        if ((tok-p[i])*t[i]>=tok) 
        {
            tok=(tok-p[i])*t[i];
            tok=min(tok, (long long)1e15);
            res.push_back(i);
        } else
            break;
    }

    a.erase(a.begin(), a.begin()+(int)res.size());

    solve(0, tok, 4, a, b, p, t);

    for(auto i: best)
        res.push_back(i);

    for(int i = 0; i < best1; i++) {
        res.push_back(b[i].second);
    }
    return res;
}

• 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