제출 #617780

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

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

long long arr[MAX] , dp[MAX] ;
long long val[MAX] , pref[MAX] ;

vector<int>v[2] ;

int n , m ;

void solve(bool t)
{
	if(!v[!t].size())
	{
		for(auto &i : v[t])
			dp[i] = 1e18 ;
		return ; 
	}
	int st = arr[v[t][0]] , sz = v[!t].size() ;
	long long sum = 0 , Min = dp[v[!t][sz-1]] ;
	for(int j = sz-1 ; j >= 0 ; --j)
	{
		int i = v[!t][j] ;
		sum += st - arr[i] ;
		Min = min(Min , dp[i-1]) ;
		val[i] = Min + sum ;
	}
	pref[v[!t][0]] = val[v[!t][0]] ;
	for(int j = 1 ; j < sz ; ++j)
	{
		int i = v[!t][j] ;
		pref[i] = min(pref[i-1] , val[i]) ;
	}
	int j = v[t][0]-1 ;
	sum = 0 , Min = 1e18 ;
	for(auto &i : v[t])
	{
		Min += arr[v[t][0]] - arr[v[t][0]-1] , sum += arr[i] - st ;
		dp[i] = Min ;
		if(j >= v[!t][0])
			dp[i] = min(Min , pref[j]) , Min = min(Min , val[j]) ;
		dp[i] += sum ;
		--j ;
	}
}

long long min_total_length(std::vector<int> r, std::vector<int> b) 
{
	n = r.size() , m = b.size() ;
	vector< pair<int , int> >vp ;
	for(auto &i : r)
		vp.emplace_back(i , 0) ;
	for(auto &i : b)
		vp.emplace_back(i , 1) ;
	sort(vp.begin() , vp.end()) ;
	int prv = vp[0].second , idx = 0 ;
	for(auto &p : vp)
	{
		++idx ;
		arr[idx] = p.first ;
		if(p.second != prv)
			solve(prv) , v[!prv].clear() ;
		v[p.second].push_back(idx) ;
		prv = p.second ;
	} 
	solve(prv) ;
	return dp[n+m] ;
}

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