제출 #1158995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158995		emptypringlescan	전선 연결 (IOI17_wiring)	C++20	100 / 100	24 ms	10780 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"
vector<pair<long long,int> > arr;
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;
	int pst=0,curst=1;
	long long back[200005],pref[200005],best,cur,sum;
	for(int i=1; i<(int)arr.size(); i++){
		if(i!=1&&arr[i].second!=arr[i-1].second){
			cur=0; best=1e16; sum=0;
			pst=curst;
			curst=i;
			long long cursm=0;
			for(int j=i-1; j>=pst; j--){
				cursm+=arr[j].first;
				back[j]=min(dp[j-1],dp[j])-cursm-(long long)j*arr[i].first;
			}
			pref[pst]=back[pst];
			for(int j=pst+1; j<i; j++) pref[j]=min(back[j],pref[j-1]);
		}
		if(!pst) continue;
		int l=i-curst+1;
		sum+=arr[i].first;
		if(l<=curst-pst){
			cur-=arr[curst-l].first;
			best=min(best-arr[curst-1].first,cur+min(dp[curst-l],dp[curst-l-1]));
		}
		else best-=arr[curst-1].first;
		dp[i]=sum+best;
		if(curst-l>=pst){
			int x=curst-l;
			dp[i]=min(dp[i],sum+pref[x]+(long long)(curst-l)*arr[curst].first);
		}
	}
	return dp[(int)arr.size()-1];
}

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