Submission #1051326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051326		deera	Jobs (BOI24_jobs)	C++14	11 / 100	173 ms	41756 KiB

Main

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

typedef long long ll;

vector<ll> profit;
vector<set<ll>> children;

ll profit_dp(ll node) {
    // childrens_profit = sum of positive profits of children
    // return max(profit[node] + childrens_profit, 0)

    ll cp = 0;
    for(auto child : children[node]) {
        cp += max(profit_dp(child), 0ll);
    }

    return max(profit[node] + cp, 0ll);
}

int main() {
    ll n, s;
    cin >> n >> s;

    profit.resize(n+1);
    children.resize(n+1);

    
    for(ll i = 0 ; i < n; i++) {
        ll x, p;
        cin >> x >> p;

        profit[i+1] = x;
        children[p].insert(i+1);
    }

    cout << profit_dp(0) << endl;
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31