Submission #1051593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051593		deera	Jobs (BOI24_jobs)	C++14	40 / 100	203 ms	54768 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
 
vector<ll> profit;
vector<vector<ll>> children;
vector<pair<ll, ll>> res;
const ll z = 0ll;

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

	ll sum = 0;
	for(auto child: children[node]) sum += non_neg(profit_dp(child));
	return non_neg(profit[node] + sum);
}
 
void dp(ll node, ll p, ll hi, ll lo) {
	p += profit[node];
	if(p > hi) res.push_back({lo - hi, p - hi});
	for(auto child: children[node]) dp(child, p, max(hi, p), min(lo, p));
}

void solve() {
	ll n, s;
	cin >> n >> s;

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

	for(ll i = 0; i < n; i++){
		int x, p;
		cin >> x >> p;
		
		profit[i+1] = x;
		children[p].push_back(i+1);
	}

	if(s == 1000000000000000000ll) return (void)(cout << profit_dp(0));
	
	for(auto start: children[0]) dp(start, z, z, z);

	sort(rall(res));

	ll a = 0;
	for(auto r: res){
		if (r.first + s < 0) break;
		s += r.second;
		a += r.second;
	}
	cout << a;
}
 
int main() {solve(); cout << endl;}

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