Submission #1025517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025517		pcc	Jobs (BOI24_jobs)	C++17	29 / 100	228 ms	150440 KiB

Main

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

#define int ll
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const ll mxn = 3e5+10;
ll N,S;
ll arr[mxn];
vector<int> tree[mxn],tree2[mxn],tree3[mxn];
ll dp[mxn];
priority_queue<pll,vector<pll>,less<pll>> son[mxn];

void dfs(int now,int top = 0){
	dp[top] += arr[now];
	for(auto nxt:tree[now]){
		if(arr[nxt]<0){
			tree2[top].push_back(nxt);
			dfs(nxt,nxt);
		}
		else{
			dfs(nxt,top);
		}
	}
}

void dfs2(int now){
	assert(!now||tree2[now].size()<2);
	for(auto nxt:tree2[now]){
		dfs2(nxt);
		//cerr<<"TREE2: "<<now<<','<<nxt<<':'<<arr[nxt]<<' '<<dp[nxt]<<endl;
		son[now].push(pll(arr[nxt]+arr[now],nxt));
	}
	while(dp[now]<=0&&!son[now].empty()){
		auto [dep,tar] = son[now].top();son[now].pop();
		if(dp[tar]<0)continue;
		arr[now] = min(arr[now],dep);
		dp[now] += dp[tar];
		while(!son[tar].empty()){
			auto [__,nxt] = son[tar].top();
			son[tar].pop();
			son[now].push(pll(dep+arr[nxt],nxt));
		}
	}
	return;
}


void dfs3(int now){
	cerr<<now<<":"<<arr[now]<<','<<dp[now]<<endl;
	while(!son[now].empty()){
		tree3[now].push_back(son[now].top().sc);
		son[now].pop();
	}
	for(auto nxt:tree3[now]){
		cerr<<now<<','<<nxt<<endl;
		dfs3(nxt);
	}
	return;
}

priority_queue<pll,vector<pll>,less<pll>> pq;
vector<int> heads;
vector<deque<pll>> v;

deque<pll> trim(int l,int r){
	deque<pll> re;
	re.push_back(pll(0,0));
	for(int i = l;i<=r;i++){
		if(arr[i]>=0)re.back().sc+=arr[i];
		else{
			if(re.back().sc>=0){
				re.push_back(pll(arr[i],arr[i]));
			}
			else{
				re.back().sc += arr[i];
			}
		}
		re.back().fs = min(re.back().fs,re.back().sc);
	}
	assert(!re.empty());
	return re;
}

main(){
	cin>>N>>S;
	for(int i = 1;i<=N;i++){
		ll x,p;
		cin>>x>>p;
		arr[i] = x;
		if(!p)heads.push_back(i);
	}
	heads.push_back(N+1);
	for(int i = 0;i+1<heads.size();i++){
		v.push_back(trim(heads[i],heads[i+1]-1));
	}
	for(int i = 0;i<v.size();i++){
		pq.push(pll(v[i].front().fs,i));
	}
	ll ans = 0;
	while(!pq.empty()&&S+pq.top().fs>=0){
		auto [val,id] = pq.top();
		pq.pop();
		if(v[id].front().sc<0)continue;
		ans += v[id].front().sc;
		S += v[id].front().sc;
		v[id].pop_front();
		if(!v[id].empty()){
			pq.push(pll(v[id].front().fs,id));
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

Main.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:97:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0;i+1<heads.size();i++){
      |                ~~~^~~~~~~~~~~~~
Main.cpp:100:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::deque<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~

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