Submission #641990

#	Time	Username	Problem	Language	Result	Execution time	Memory
641990		QwertyPi	Wiring (IOI17_wiring)	C++14	100 / 100	59 ms	13392 KiB

wiring

#include "wiring.h"
 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
 
int ps[200001];
int pre[200001][2];
int dp[200001];
vector<pair<int, int>> vp;
int sum(int l, int r){
	return ps[r + 1] - ps[l];
}
 
int n, m;
int cost(int l, int r){
	assert(l < r && l >= 0 && r < n + m);
	int lr = pre[r][!vp[r].se];
	int lsz = lr - l + 1;
	int rsz = r - lr;
	int _m = min(lsz, rsz);
	int ret = sum(lr + 1, lr + _m) - sum(lr - _m + 1, lr);
	if(lsz >= rsz){
		return ret + (lsz - rsz) * vp[lr + 1].fi - sum(l, lr - _m);
	}else{
		return ret + sum(lr + _m + 1, r) - (rsz - lsz) * vp[lr].fi;
	}
}
 
long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
  	n = r.size(); m = b.size();
	for(int i = 0; i < n; i++) vp.push_back({r[i], 0});
	for(int i = 0; i < m; i++) vp.push_back({b[i], 1});
	sort(vp.begin(), vp.end());
 
	for(int i = 0; i < n + m; i++){
		ps[i + 1] = ps[i] + vp[i].fi;
	}
	
	for(int i = 0; i < n + m; i++){
		pre[i][vp[i].se] = i;
		pre[i][!vp[i].se] = (i == 0 ? -1 : pre[i - 1][!vp[i].se]);
	}
 
	dp[0] = 0;
	fill(dp + 1, dp + n + m + 1, 1LL << 60);
	int opt = -1;
	for(int i = 0; i < n + m; i++){
		if(pre[i][!vp[i].se] == -1) continue;
		if(vp[i].se != vp[i - 1].se) opt = dp[pre[i][!vp[i].se] + 1] == 1LL << 60 ? 0 : pre[i][!vp[i].se];
		while(opt > 0 && vp[opt - 1].se != vp[i].se && min(dp[opt], dp[opt - 1]) + cost(opt - 1, i) <= dp[opt] + cost(opt, i)) opt--;
		dp[i + 1] = min(dp[opt + 1], dp[opt]) + cost(opt, i);
	}
	return dp[n + m];
}

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