Submission #1051321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051321		deera	Jobs (BOI24_jobs)	C++14	0 / 100	53 ms	29776 KiB

Main

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

vector<int> profit;
vector<set<int>> children;

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

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

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

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

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

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

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

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

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