Submission #1161623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161623		zolw	Job Scheduling (IOI19_job)	C++20	0 / 100	3095 ms	327680 KiB

job

#include "job.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

const int N = 2e5+5432, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321, mod = 998244353;

struct Element
{
	ll u,t;
	bool operator < (const Element &element) const
	{
		return t*element.u < element.t*u;
	}
};

ll n;
ll P[N], U[N], T[N];
vector<Element> A[N];
vector<ll> G[N];

void DFS(ll v)
{
	for(auto x : G[v])
	{
		DFS(x);

		int wsk = -1, dod = -1;
		vector<Element> P;

		for(auto y : A[x])
		{
			Element akt = {0,0};
			int wsk2 = wsk;
			for(int i = wsk2+1; i < (int)A[v].size(); ++i)
			{
				akt = {akt.u+A[v][i].u,akt.t+A[v][i].t};
				if(akt < y)
				{
					wsk = i;
					akt = {0,0};
				}
			}
			while(dod < wsk) ++dod, P.pb(A[v][dod]);
			P.pb(y);
		}

		while(dod+1 < (int)A[v].size()) ++dod, P.pb(A[v][dod]);
		A[v] = P;
	}
	vector<Element> akt = {{U[v],T[v]}};
	for(auto x : A[v]) akt.pb(x);
	A[v] = akt;
}

long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	n = (ll)p.size();
	rep(i,n) P[i] = p[i], U[i] = u[i], T[i] = d[i];

	for(int i = 1; i < n; ++i)
	{
		G[P[i]].pb(i);
	}

	DFS(0);	

	ll t = 0, ans = 0;
	for(auto x : A[0])
	{
		t += x.t;
		ans += t*x.u;
	}

	return ans;
}

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