Submission #1269314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269314		sula2	Festival (IOI25_festival)	C++20	24 / 100	51 ms	7480 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(), c = 0, z = 0, d = 0, j = 0;
    vector<int> l[3];
    for (int i = 0; i < n; i++) {
        l[t[i]].push_back(i);
    }
    for (int i = 1; i <= 2; i++)
        sort(l[i].begin(), l[i].end(), [&](int x, int y) { return p[x] < p[y]; });
    vector<long long> s{ 0 };
    for (int i : l[1])
        s.push_back(s.back() + p[i]), z++;
    long long x = a;
    while (s[z] > x) z--;
    c = z;
    for (int i : l[2]) {
        x = min((long long)1e18, (x - p[i])*t[i]);
        if (x < 0) break;
        while (s[z] > x) z--;
        while (z+1 < s.size() && s[z+1] <= x) z++;
        j++;
        if (j + z > c + d)
            c = z, d = j;
    }
    while (l[2].size() > d) l[2].pop_back();
    for (int i = 0; i < c; i++)
        l[2].push_back(l[1][i]);
    return l[2];
}

• 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