Submission #885991

#	Time	Username	Problem	Language	Result	Execution time	Memory
885991		waldi	Wiring (IOI17_wiring)	C++17	100 / 100	41 ms	15304 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define inf 1000000000000000000ll
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, bool> plb;

vector<ll> pom(vector<ll> popdp, vector<ll> poppoz, vector<ll> terpoz){
	//~ printf("poppoz: ");
	//~ for(ll x : poppoz) printf("%lld ", x);
	//~ printf("\n");
	//~ printf("popdp: ");
	//~ for(ll x : popdp) printf("%lld ", x);
	//~ printf("\n");
	
	//~ printf("terpoz: ");
	//~ for(ll x : terpoz) printf("%lld ", x);
	//~ printf("\n");
	
	int n = ssize(poppoz);
	int m = ssize(terpoz);
	
	ll dodaj = 0ll;
	for(int i = n-1; ~--i;){
		dodaj += poppoz[n-1]-poppoz[i];
		popdp[i] += dodaj;
	}
	
	ll delta = terpoz[0]-poppoz[n-1];
	
	vector<ll> mini_pref(n);
	REP(i, n){
		mini_pref[i] = popdp[i] + delta*(n-i);
		if(i) mini_pref[i] = min(mini_pref[i], mini_pref[i-1]);
	}
	
	vector<ll> mini_suff(n);
	for(int i = n; ~--i;){
		mini_suff[i] = popdp[i];
		if(i+1 < n) mini_suff[i] = min(mini_suff[i], mini_suff[i+1]);
	}
	
	vector<ll> dp(m+1);
	dp[0] = popdp[n];
	FOR(i, 1, m){
		dp[i] = inf;
		if(n-i > 0) dp[i] = min(dp[i], mini_pref[n-i-1]);
		dp[i] = min(dp[i], mini_suff[max(0, n-i)] + delta*i);
		
		dp[i] = min(dp[i], popdp[n] + delta*i);
	}
	
	dodaj = 0ll;
	FOR(i, 2, m){
		dodaj += terpoz[i-1]-terpoz[0];
		dp[i] += dodaj;
	}
	
	//~ printf("dp: ");
	//~ for(ll x : dp) printf("%lld ", x);
	//~ printf("\n");
	
	//~ printf("\n");
	return dp;
}

ll min_total_length(vector<int> r, vector<int> b){
	vector<plb> vec;
	for(int x : r) vec.emplace_back(x, 0);
	for(int x : b) vec.emplace_back(x, 1);
	sort(all(vec));
	
	vector<ll> dp, poppoz, terpoz;
	REP(i, ssize(vec)){
		terpoz.emplace_back(vec[i].fi);
		if(i+1 == ssize(vec) || vec[i+1].se != vec[i].se){
			if(dp.empty()) dp.resize(ssize(terpoz)+1, inf), dp[0] = 0ll;
			else dp = pom(dp, poppoz, terpoz);
			poppoz = terpoz, terpoz.clear();
		}
	}
	return dp.back();
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45