Submission #1051331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051331		deera	Jobs (BOI24_jobs)	C++14	11 / 100	269 ms	37712 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;

    if (s == 1000000000000000000ll) {

        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