Submission #994699

#	Time	Username	Problem	Language	Result	Execution time	Memory
994699		PenguinsAreCute	Jobs (BOI24_jobs)	C++17	29 / 100	184 ms	55568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 314159;
int pr[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
vector<pair<int,int>> op;
void dfs(int x, int prof, int maxProf, int loss) {
	vis[x]=1;
	if(prof+pr[x]>maxProf) op.push_back({loss-maxProf,prof+pr[x]-maxProf});
	for(auto i: adj[x]) dfs(i,prof+pr[x],max(maxProf,prof+pr[x]),min(loss,prof+pr[x]));
}
main() {
	int n, s, ans = 0; cin >> n >> s;
	for(int i=1,p;i<=n;i++) {cin>>pr[i]>>p; adj[p].push_back(i);}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0,0,0);
	sort(op.begin(),op.end(),greater<pair<int,int>>());
	for(int i=0;i<op.size()&&op[i].first+s>=0;i++) s+=op[i].second, ans+=op[i].second;
	cout << ans;
}

Compilation message (stderr)

Main.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:19:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<op.size()&&op[i].first+s>=0;i++) s+=op[i].second, ans+=op[i].second;
      |              ~^~~~~~~~~~

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