내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

c++

#include <bits/stdc++.h>

#define MAX_N 262150
#define ll long long
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) begin(a), end(a)
using namespace std;

ll n, id[MAX_N], no;
vpll po;

void dfs(ll u, ll d) {
    if (u * 2 <= n)
        dfs(u * 2, d + 1);
    id[u] = no++;
    po.push_back({d, 0});
    if (u * 2 + 1 <= n)
        dfs(u * 2 + 1, d + 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dfs(1, 0);
    ll res = INT_MIN;
    for (ll i = 1; i <= n; i++) {
        cin >> po[id[i]].second;
        res = max(res, po[id[i]].second);
    }

    for (ll i = 0; i < 20; i++) {
        for (ll j = i; j < 20; j++) {
            ll ma = INT_MIN;
            for (ll k = 0; k < n; k++) {
                if (po[k].first < i or po[k].first > j) continue;
                ma = max(po[k].second, ma + po[k].second);
                res = max(res, ma);
            }
        }
    }
    
    cout << res;

    return 0;
}