Rating Choices

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const long long INF = 1e17; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; ll cur; cin >> n >> cur;
    10    ll node = (1 << (n + 1)) - 1, m = (1 << n) - 1;
    11    vector<array<pair<int, int>, 2>> adj(node + 1);
    12    vector<bool> leaf(node + 1);
    13    for (int i = 0; i < m; i++) {
    14        int u, v, w, d; cin >> u >> v >> w >> d;
    15        leaf[u] = 1; // not leaf
    16        adj[u][0] = {v, d}; //take
    17        adj[u][1] = {w, 0}; //skip
    18    }
    19    ll ans = -INF;
    20    auto dfs = [&] (auto &&self, int u, ll best) -> void {
    21        if (!leaf[u]) { //is leaf
    22            ans = max(ans, best);
    23            return;
    24        }
    25        self(self, adj[u][0].first, best + adj[u][0].second);
    26        self(self, adj[u][1].first, best + adj[u][1].second);
    27    };
    28    dfs(dfs, 1, cur);
    29    cout << ans << '\n';
    30    return 0;
    31}