제출 #1161448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161448		zolw	Job Scheduling (IOI19_job)	C++20	0 / 100	3093 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 = 0, wsk2 = 0;
		vector<Element> P;
		while(wsk < (int)A[v].size() or wsk2 < (int)A[x].size())
		{
			if(wsk == (int)A[v].size()) P.pb(A[x][wsk2]), ++wsk2;
			else if(wsk2 == (int)A[x].size()) P.pb(A[v][wsk]), ++wsk;
			else if(A[x][wsk2] < A[v][wsk]) P.pb(A[x][wsk2]), ++wsk2;
			else P.pb(A[v][wsk]), ++wsk;
		}
		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