Submission #1193808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193808		chaeryeong	Job Scheduling (IOI19_job)	C++20	0 / 100	307 ms	327680 KiB

job

#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;
vector <int> dp[MAXN];
vector <int> merge (vector <int> x, vector <int> y) {
	vector <int> ret;
	while (!x.empty() && !y.empty()) {
		//-d[x.back()] * u[y.back()]
		//-d[y.back()] * u[x.back()]

		if (-d[x.back()] * u[y.back()] > -d[y.back()] * u[x.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);
		dp[pos] = merge(dp[pos], dp[j]);
	}
	dp[pos].insert(dp[pos].begin(), 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;
}

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