제출 #1158708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158708		emptypringlescan	Wiring (IOI17_wiring)	C++20	0 / 100	1096 ms	7608 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
vector<pair<long long,int> > arr;
long long cost(int l, int r){
	long long ret=0;
	if(arr[l].second==arr[r].second) return 1e16;
	int c1=l,c2=r;
	long long v1=0,v2=0;
	while(arr[c1].second==arr[l].second||arr[c2].second==arr[r].second){
		if(arr[c1].second!=arr[l].second) ret+=arr[c2].first-v1;
		else if(arr[c2].second!=arr[r].second) ret+=v2-arr[c1].first;
		else{
			ret+=arr[c2].first-arr[c1].first;
			v1=arr[c1].first; v2=arr[c2].first;
		}
		c1++; c2--;
	}
	return ret;
}
long long min_total_length(vector<int> r, vector<int> b){
	arr.push_back({-1,-1});
	int c1=0,c2=0;
	while(c1<(int)r.size()||c2<(int)b.size()){
		if(c1==(int)r.size()){
			arr.push_back({b[c2],1});
			c2++;
		}
		else if(c2==(int)b.size()){
			arr.push_back({r[c1],0});
			c1++;
		}
		else if(r[c1]<b[c2]){
			arr.push_back({r[c1],0});
			c1++;
		}
		else{
			arr.push_back({b[c2],1});
			c2++;
		}
	}
	long long dp[200005];
	for(int i=0; i<200005; i++) dp[i]=1e16;
	dp[0]=0;
	for(int i=1; i<(int)arr.size(); i++){
		bool changed=false;
		for(int j=i-1; j>0; j--){
			if(arr[j].second!=arr[i].second) changed=true;
			else if(changed==true) break;
			else continue;
			dp[i]=min(dp[i],dp[j-1]+cost(j,i));
		}
	}
	return dp[(int)arr.size()-1];
}

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