Submission #1197576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197576		cbd_6969	Jobs (BOI24_jobs)	C++20	100 / 100	344 ms	105808 KiB

Main

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

const int N=3e5+5;
int n, m, a[N];
vector<int> adj[N];

struct DP:map<int, int>{
	void pop(int x){
		int cur=-x, last=x;
		for(map<int, int>::iterator it=begin();it!=end()&&cur<0;it=erase(it)){
            if(cur<0){
            	last=max(last, it->first-cur);
			}
            cur+=it->second;
        }
        if(cur>0){
        	(*this)[last]+=cur;
		}
	}
}dp[N];

void dfs(int u){
	for(int v:adj[u]){
		dfs(v);
		if(dp[v].size()>dp[u].size()) swap(dp[u], dp[v]);
		for(pair<int, int> p:dp[v]){
			int x=p.first, y=p.second;
			dp[u][x]+=y;
		}
	}
	if(a[u]>=0){
		dp[u][0]+=a[u];
	}
	else dp[u].pop(-a[u]);
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		int p;
		cin>>a[i]>>p;
		adj[p].push_back(i);
	}
	dfs(0);
	int ans=0;
	for(pair<int, int> p:dp[0]){
		int x=p.first, y=p.second;
		if(x<=m){
			m+=y;
			ans+=y;
		}
	}
	cout<<ans;
}

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