제출 #641989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641989		QwertyPi	전선 연결 (IOI17_wiring)	C++14	0 / 100	1 ms	312 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) {
	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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45