Submission #202383

#	Time	Username	Problem	Language	Result	Execution time	Memory
202383		blackbori	Job Scheduling (IOI19_job)	C++14	100 / 100	302 ms	46540 KiB

job

#include "job.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct job{
	ll s, d;
	job(ll s, ll d) : s(s), d(d) {}
	job() {}
	bool operator < (job t) const {
		return s * t.d < d * t.s; }
};

priority_queue <job> S[202020];
vector <int> T[202020];
ll ans;

void merge(int u, int v)
{
	auto &P = S[u], &Q = S[v];
	if(P.size() < Q.size()) swap(P, Q);
	for(; !Q.empty(); Q.pop()) P.push(Q.top());
}

void insert(int i, job x)
{
	auto &P = S[i];
	for(; !P.empty(); P.pop()){
		job t = P.top();
		if(t < x) break; 
		ans += t.s * x.d;
		x.s += t.s; x.d += t.d;
	}
	P.push(x);
}

ll scheduling_cost(vector <int> P, vector <int> U, vector<int> D)
{
	int n, i;

	n = P.size();
	for(i = 0; i < n; i ++){
		if(i) T[P[i]].push_back(i);
		ans += U[i] * D[i];
	}

	for(i = n - 1; i >= 0; i --){
		for(int &t: T[i]){
			merge(i, t);
		}
		insert(i, job(U[i], D[i]));
	}

	insert(0, job(-2e9, 0));

	return ans;
}

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