Submission #1158988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158988		emptypringlescan	Wiring (IOI17_wiring)	C++20	13 / 100	24 ms	10684 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(pref[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: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45