| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 331181 | 2020-11-27T16:44:44 Z | ttnhuy313 | Job Scheduling (IOI19_job) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, sum_cost[N], sum_d[N], dp[N], cost[N], d[N];
vector <int> adj[N];
void dfs(int u) {
sum_cost[u] = cost[u];
sum_d[u] = d[u];
vector <int> V; V.clear();
for (int v : adj[u]) {
V.push_back(v);
dfs(v);
sum_cost[u] += sum_cost[v];
sum_d[u] += sum_d[v];
}
sort(V.begin(), V.end(), [](int i, int j) {
return sum_d[i] * sum_cost[j] < sum_d[j] * sum_cost[i];
});
dp[u] = d[u] * cost[u];
int pre = d[u];
for (int v : V) {
dp[u] += dp[v] + pre * sum_cost[v];
pre += sum_d[v];
}
}
int scheduling_cost(vector <int> p, vector <int> c, vector <int> time) {
n = p.size();
for (int i = 0; i < n; ++i) {
cost[i] = c[i];
d[i] = time[i];
}
for (int i = 1; i < n; ++i) {
adj[p[i]].push_back(i);
}
dfs(0);
return dp[0];
}