제출 #170184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170184		dennisstar	전선 연결 (IOI17_wiring)	C++11	0 / 100	3 ms	1148 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

ll min_total_length(vim r, vim b) {
	int n=r.size(), m=b.size();
	vector<ll> D(n+m), sr(n+m), sb(n+m);
	vim lst(200010);
	vector<pii> ar;
	for (int i:r) ar.push_back({i, 0});
	for (int i:b) ar.push_back({i, 1});
	sort(ar.begin(), ar.end());
	fill(lst.begin(), lst.end(), -1);
	for (int i=0; i<n+m; i++) {
		if (i) sr[i]=sr[i-1], sb[i]=sb[i-1];
		if (ar[i].se==0) sr[i]+=ar[i].fi;
		else sb[i]+=ar[i].fi;
	}

	int x=0, y[]={-1,-1};
	y[ar[0].se]=ar[0].fi;
	for (int i=1; i<n+m; i++) {
		if (ar[i].se==0) x++;
		else x--;
		int l=lst[x+100000];
		D[i]=(1ll<<60);
		if (l!=-1) D[i]=D[l]+abs((sr[i]-sr[l])-(sb[i]-sb[l]));
		lst[x+100000]=i;
		if (i) D[i]=min(D[i], D[i-1]+ar[i].fi-(y[1-ar[i].se]==-1?ar[i].fi:y[1-ar[i].se]));
		y[ar[i].se]=ar[i].fi;
	}
	return D.back();
}

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