Submission #1269311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269311		sula2	Festival (IOI25_festival)	C++20	24 / 100	51 ms	7476 KiB

festival

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

vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
    int n = p.size();
    vector<int> ind[3];
    for (int i = 0; i < n; i++) {
        ind[t[i]].push_back(i);
    }
    for (int i = 1; i <= 2; i++) 
        sort(ind[i].begin(), ind[i].end(), [&](int x, int y) { return p[x] < p[y]; });
    vector<long long> pr{ 0 };
    for (int i : ind[1])
        pr.push_back(pr.back() + p[i]);
    long long tokens = a;
    int ptr = pr.size() - 1;
    while (pr[ptr] > tokens) ptr--;
    int c1 = ptr, c2 = 0, j = 0;
    for (int i : ind[2]) {
        tokens = min((long long)1e18, (tokens - p[i])*t[i]);
        if (tokens < 0) break;
        while (pr[ptr] > tokens) ptr--;
        while (ptr+1 < pr.size() && pr[ptr+1] <= tokens) ptr++;
        j++;
        if (j + ptr > c1 + c2) {
            c1 = ptr;
            c2 = j;
        }
    }
    vector<int> ans;
    for (int i = 0; i < c2; i++)
        ans.push_back(ind[2][i]);
    for (int i = 0; i < c1; i++)
        ans.push_back(ind[1][i]);
    return ans;
}

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