제출 #262150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262150		sjimed	전선 연결 (IOI17_wiring)	C++14	100 / 100	69 ms	8836 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define pre(a) cout << fixed; cout.precision(a)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
ll c[200010];
ll dp[200010];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	n = r.size() + b.size();

	vector<pii> v;
	v.eb(-inf, 0);
	for(auto i : r) v.eb(i, 0);
	for(auto i : b) v.eb(i, 1);

	sort(all(v));

	ll R = -INF, B = -INF; 
	for(int i=1; i<=n; i++) {
		if(v[i].se == 0) R = v[i].fi;
		else B = v[i].fi;

		c[i] = abs(R - B);
	}

	R = INF, B = INF; 
	for(int i=n; i > 0; i--) {
		if(v[i].se == 0) R = v[i].fi;
		else B = v[i].fi;

		c[i] = min(c[i], abs(R - B));
	}

	int t = 0;
	ll sum = 0;
	for(int i=1; i<=n; i++) {
		dp[i] = dp[i-1] + c[i];
		
		if(i-1 > 0 && v[i-1].se != v[i].se) {
			t = 1;
			sum = v[i].fi - v[i-1].fi;
			dp[i] = min(dp[i], dp[i-2] + sum);
		}
		else if(i-2*t-1 > 0 && v[i-2*t-1].se != v[i].se) {
			t++;
			sum += v[i].fi - v[i-2*t+1].fi;
			dp[i] = min(dp[i], dp[i-2*t] + sum);
		}
		else t = 0, sum = 0;
	}

	return dp[n];
}

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