제출 #331182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331182		ttnhuy313	Job Scheduling (IOI19_job)	C++14	24 / 100	143 ms	58476 KiB

job

#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 <int32_t> p, vector <int32_t> c, vector <int32_t> 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];
}


// signed main() {
// 	ios_base::sync_with_stdio(0); cin.tie(0);
// 	freopen("JOB.INP", "r", stdin);
// 	freopen("JOB.OUT", "w", stdout);

// 	int n;
// 	cin >> n;
// 	vector <int32_t> p, c, time;
// 	p.assign(n, 0); c.assign(n, 0); time.assign(n, 0);
// 	for (int i = 0; i < n; ++i) {
// 		cin >> p[i];
// 	}
// 	for (int i = 0; i < n; ++i)
// 		cin >> c[i];
// 	for (int i = 0; i < n; ++i)
// 		cin >> time[i];
// 	cout << scheduling_cost(p, c, time) << endl;

// 	return 0;
// }

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 37