제출 #1129002

#제출 시각아이디문제언어결과실행 시간메모리
1129002nhanhoang510Jobs (BOI24_jobs)C++20
11 / 100
124 ms26948 KiB
#include <bits/stdc++.h> #define F first #define S second using namespace std; const int maxn = 3 * 1e5 + 7; const int LOG = 20; const long long MOD = (long long)(1e9) + 7; const long long base = 311; const int ALP_BET = 26; typedef pair<int, int> ii; typedef pair<int, long long> il; typedef pair<long long, int> li; typedef pair<long long, long long> ll; int n, m; long long a[maxn], s; int p[maxn]; vector<int> adj[maxn]; int root[maxn]; namespace BUFFALO{ const int maxN = 10 + 7; bool ok[maxN]; int arr[maxN]; long long ans; void solve(){ for(int i = 1; i <= n; ++i) arr[i] = i; ans = s; do{ memset(ok, false, sizeof(ok)); long long sum = s; for(int i = 1; i <= n; ++i){ int u = arr[i]; if(p[u] != 0 && !ok[p[u]]) break; ok[u] = true; sum = sum + a[u]; if(sum < 0) break; ans = max(ans, sum); } } while(next_permutation(arr + 1, arr + n + 1)); cout << ans - s << "\n"; return; } } namespace SUB1{ long long dp[maxn]; void dfs(int u){ dp[u] = a[u]; for(int v : adj[u]){ dfs(v); dp[u] = dp[u] + dp[v]; } dp[u] = max(dp[u], 0LL); return; } void solve(){ long long ans = 0; for(int i = 1; i <= m; ++i){ dfs(root[i]); ans += dp[root[i]]; } cout << ans << "\n"; return; } } namespace SUB3{ typedef pair<long long, long long> item; int nn; item path[maxn]; void dfs(int u, long long ss, long long maxadd, long long maxsub){ ss = ss + a[u]; if(ss > maxadd){ ++nn; path[nn] = {maxsub, ss - maxadd}; maxadd = ss; } maxsub = max(maxsub, -ss); if(!adj[u].empty()){ dfs(adj[u][0], ss, maxadd, maxsub); } return; } void solve(){ nn = 0; for(int i = 1; i <= m; ++i){ int u = root[i]; dfs(u, 0, 0, 0); } // cerr << nn << "\n"; // for(int i = 1; i <= nn; ++i){ // cerr << path[i].F << " " << path[i].S << "\n"; // } long long ans = 0; sort(path + 1, path + nn + 1); for(int i = 1; i <= nn; ++i){ long long limit = path[i].F, val = path[i].S; if(limit > s) break; ans = ans + val; } cout << ans << "\n"; return; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("Jobs.INP","r",stdin); // freopen("Jobs.OUT","w",stdout); cin >> n >> s; m = 0; for(int i = 1; i <= n; ++i){ cin >> a[i] >> p[i]; if(p[i] == 0){ ++m; root[m] = i; } else{ adj[p[i]].push_back(i); } } bool sub1 = true; long long ss = s; for(int i = 1; i <= n; ++i) if(a[i] < 0){ ss = ss + a[i]; } if(ss < 0) sub1 = false; // SUBTASK if(n <= 10){ BUFFALO::solve(); } else if(sub1){ SUB1::solve(); } else SUB3::solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...