Submission #1193969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193969		chaeryeong	Job Scheduling (IOI19_job)	C++20	21 / 100	3104 ms	239012 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;
deque <int> dp[MAXN];
deque <int> merge (deque <int> x, deque <int> y) {
	ll aux[(int)x.size() + 1][(int)y.size() + 1] = {};
	deque <ll> f((int)x.size() + 1, 0), g((int)y.size() + 1, 0);
	for (int i = (int)x.size() - 1; i >= 0; i--) {
		f[i] = f[i + 1] + u[x[i]];
	}
	for (int i = (int)y.size() - 1; i >= 0; i--) {
		g[i] = g[i + 1] + u[y[i]];
	}
	for (int i = (int)x.size() - 1; i >= 0; i--) {
		for (int j = (int)y.size() - 1; j >= 0; j--) {
			aux[i][j] = min(aux[i + 1][j] + d[x[i]] * g[j], aux[i][j + 1] + d[y[j]] * f[i]);
		}
	}
	deque <int> ret;
	int a = 0, b = 0;
	while (a < (int)x.size() && b < (int)y.size()) {
		if (aux[a][b] == aux[a + 1][b] + d[x[a]] * g[b]) {
			ret.push_back(x[a++]);
		} else {
			ret.push_back(y[b++]);
		}
	}
	while (a < (int)x.size() || b < (int)y.size()) {
		if (a < (int)x.size()) {
			ret.push_back(x[a++]);
		} else {
			ret.push_back(y[b++]);
		}
	}
	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;
}

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