제출 #1193844

#제출 시각아이디문제언어결과실행 시간메모리
1193844chaeryeongJob Scheduling (IOI19_job)C++20
0 / 100
3101 ms305636 KiB
#include "job.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 25; vector <int> adj[MAXN]; ll u[MAXN], d[MAXN]; int n, FFFF; deque <int> dp[MAXN]; deque <int> merge (deque <int> x, deque <int> y) { deque <int> ret; while (!x.empty() && !y.empty()) { if (u[x.back()] < u[y.back()]) { ret.push_back(x.back()); x.pop_back(); } else { ret.push_back(y.back()); y.pop_back(); } } while (!x.empty()) { ret.push_back(x.back()); x.pop_back(); } while (!y.empty()) { ret.push_back(y.back()); y.pop_back(); } reverse(ret.begin(), ret.end()); return ret; } void dfs (int pos) { for (auto j : adj[pos]) { dfs(j); if (dp[j].empty()) { swap(dp[pos], dp[j]); } else dp[pos] = merge(dp[pos], dp[j]); dp[j].clear(); } dp[pos].push_front(pos); } ll scheduling_cost(vector<int> p, vector<int> _U, vector<int> _D) { assert(!FFFF); FFFF = 1; n = (int)p.size(); for (int i = 0; i < n; i++) { u[i] = _U[i]; d[i] = _D[i]; if (p[i] != -1) { adj[p[i]].push_back(i); } } dfs(0); auto ans = dp[0]; ll sum = 0, ret = 0; for (auto i : ans) { sum += u[i]; } for (auto i : ans) { ret += sum * (ll)d[i]; sum -= u[i]; } return ret; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...