제출 #706854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706854		jeroenodb	Job Scheduling (IOI19_job)	C++14	5 / 100	62 ms	13996 KiB

job

#include "job.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
bool comp(const array<ll,2>& a, const array<ll,2>& b) {
	if(a[1]*b[0]==b[1]*a[0]) {
		return a[1]<b[1];
	}
	return a[1]*b[0] < b[1]*a[0];
}
// abcde
struct DS {
	vector<array<ll,2>> ts;
	void root(int u,int d) { // O(1)
		ts.push_back({ts.empty()?u:ts.back()[0]+u,d});
	}

	void merge(DS& o) {
		vector<array<ll,2>> together;
		auto it = ts.rbegin(), it2 = o.ts.rbegin();
		ll u = ts.back()[0];
		ll ou = o.ts.back()[0];
		while(it!=ts.rend() or it2!=o.ts.rend()) {
			if(it2==o.ts.rend() or (it!=ts.rend() and comp(*it,*it2))) {
				(*it)[0]+=ou;
				together.push_back(*it);
				++it;
				
				if(it==ts.rend()) u=0;
				else u = (*it)[0];
			} else {
				(*it2)[0]+=u;
				together.push_back(*it2);
				++it2;
				if(it2==o.ts.rend()) ou=0;
				else ou = (*it2)[0];
			}
		}

		swap(ts,together);
		reverse(all(ts));
	}
	ll ans() {
		ll res=0;
		ll pd=0;
		for(auto& [u,d] : ts) {
			res+=u*d;
		}
		return res;
	}
};
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	// merge chains?
	int n = p.size();
	// just loop backwards, and maintain those?
	vector<DS> dp(n);
	for(int i=n-1;i>=0;--i) {
		// add root
		dp[i].root(u[i],d[i]);
		if(p[i]!=-1) {
			if(dp[p[i]].ts.empty()) swap(dp[i],dp[p[i]]);
			else dp[p[i]].merge(dp[i]);
		}
	}

	return dp[0].ans() ;
}

컴파일 시 표준 에러 (stderr) 메시지

job.cpp: In member function 'll DS::ans()':
job.cpp:54:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for(auto& [u,d] : ts) {
      |             ^
job.cpp:53:6: warning: unused variable 'pd' [-Wunused-variable]
   53 |   ll pd=0;
      |      ^~

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