제출 #264229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264229		arnold518	전선 연결 (IOI17_wiring)	C++14	0 / 100	1080 ms	9096 KiB

wiring

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

int N, M;
ll A[MAXN+10], B[MAXN+10];
ll ans=0;
pll C[MAXN+10];
int P[MAXN+10];
ll dp[MAXN+10];

ll min_total_length(vector<int> _A, vector<int> _B)
{
	N=_A.size(); M=_B.size();
	for(int i=1; i<=N; i++) A[i]=_A[i-1];
	for(int i=1; i<=M; i++) B[i]=_B[i-1];
	for(int i=1; i<=N; i++) C[i]={A[i], 1};
	for(int i=1; i<=M; i++) C[i+N]={B[i], 2};

	sort(C+1, C+N+M+1);
	
	P[1]=0;
	for(int i=2; i<=N+M; i++)
	{
		if(C[i].second==C[i-1].second) P[i]=P[i-1];
		else P[i]=i-1;
	}

	ll val=0;
	for(int i=1; i<=N+M; i++)
	{
		dp[i]=INF;
		if(P[i]==0) continue;
		if(C[i].second!=C[i-1].second) val=C[i].first-C[i-1].first;
		else val+=C[i].first-C[P[i]].first;

		ll val2=0;
		for(int j=P[i]; j>=1 && C[j].second!=C[i].second; j--)
		{
			if(i-P[i]>=P[i]+1-j) val2+=C[P[i]].first-C[j].first;
			else val2+=C[P[i]+1].first-C[j].first;
			dp[i]=min(dp[i], dp[j-1]+val+val2);
		}
	}
	return dp[N+M];
}

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