Submission #1330324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330324		somefolk	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 KiB

festival

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

#define int long long
const int INF = 1e16;

struct Coupon {
    int p, t, idx;
    int apply(int tk){
        tk -= p; tk *= t;
        if (tk > INF) tk = INF;
        if (tk < 0) tk = -1;
        return tk;
    }
};

vector<signed> max_coupons(signed A, vector<signed> p, vector<signed> t){
    int a = A;
    int n = (int)p.size();

    deque<Coupon> nr, ones;
    for(int i = 0; i < n; i++){
        if(t[i] == 1) ones.push_back({p[i], t[i], i});
        else nr.push_back({p[i], t[i], i});
    }

    sort(nr.begin(), nr.end(), [&](auto left, auto right){
        return left.p * left.t * (right.t - 1) < right.p * right.t * (left.t - 1);
    });
    sort(ones.begin(), ones.end(), [&](auto left, auto right){
        return left.p < right.p;
    });

    vector<signed> sol;
    while(!nr.empty()){
        Coupon curr = nr.front();
        if(curr.apply(a) < a) break;
        a = curr.apply(a);
        sol.push_back(curr.idx);
        nr.pop_front();
    }
    const int MX = 100;
    int sz = (int)nr.size();
    vector<vector<int>> dp(sz+1, vector<int>(MX+1, -1)); dp[0][0] = a;
    vector<vector<char>> vis(sz+1, vector<char>(MX+1, 0));
    for(int i = 1; i <= sz; i++){
        Coupon curr = nr[i-1];
        for(int j = 0; j <= MX; j++) dp[i][j] = max(dp[i][j], dp[i-1][j]);
        for(int j = 1; j <= MX; j++){
            if(dp[i-1][j-1] == -1) continue;
            if(curr.apply(dp[i-1][j-1]) > dp[i][j]){
                vis[i][j] = 1;
                dp[i][j] = curr.apply(dp[i-1][j-1]);
            }
        }
    }

    vector<int> pref((int)ones.size()+1, 0);
    for(int i = 0; i < ones.size(); i++) pref[i+1] = pref[i] + ones[i].p;

    auto get = [&](int cnt){
        int idx = (int)(upper_bound(pref.begin(), pref.end(), cnt) - pref.begin());
        return max(0LL, idx-1);
    };

    int mx = 0, mxIdx = 0;
    for(int i = 0; i <= MX; i++){
        if(dp[sz][i] == -1) continue;
        if(i + get(dp[sz][i]) > mx){ mx = i + get(dp[sz][i]); mxIdx = i; }
    }

    vector<int> sol2;
    int i = sz, j = mxIdx;
    while(i > 0){
        if(j > 0 && vis[i][j]){
            sol2.push_back(nr[i-1].idx);
            i--; j--;
        } else {
            i--;
        }
    }
    reverse(sol2.begin(), sol2.end());
    for(auto &i : sol2) sol.push_back(i);

    int res = dp[sz][mxIdx];
    for(int i = 0; i < ones.size(); i++){
        if(res < ones[i].p) break;
        res = ones[i].apply(res);
        sol.push_back(ones[i].idx);
    }

 

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:90:6: error: expected '}' at end of input
   90 |     }
      |      ^
festival.cpp:17:73: note: to match this '{'
   17 | vector<signed> max_coupons(signed A, vector<signed> p, vector<signed> t){
      |                                                                         ^
festival.cpp:90:6: warning: no return statement in function returning non-void [-Wreturn-type]
   90 |     }
      |      ^