Submission #433026

#	Time	Username	Problem	Language	Result	Execution time	Memory
433026		pliam	Wiring (IOI17_wiring)	C++14	13 / 100	31 ms	4172 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXM 100005
#define INFL (ll)2e18
#define INF (int)2e9

ll dp[MAXN+MAXM];
vector<pair<ll,int>> points;//0=red,1=blue

ll min_total_length(vector<int> r, vector<int> b) {
	//merge sort
	/* for(int i=0,j=0;i<r.size()||j<b.size();){
		if(i>=r.size()||(j<b.size()&&r[i]>b[j])){
			points.push_back({b[j],1});
			j++;
		}else{
			points.push_back({r[i],0});
			i++;
		}
	}
	int pos=1;
	while(points[pos].second==points[pos-1].second) pos++;*/
	if(b[0]<r[0]) swap(b,r);
	r.push_back(INF);
	b.push_back(INF);
	int pos_r=1,pos_b=1;
	ll sumr=0,sumb=0;
	while(r[pos_r]<b[0]){
		sumr+=pos_r*((ll)r[pos_r]-r[pos_r-1]);
		pos_r++;
	}
	ll dist=b[0]-r[pos_r-1];
	while(b[pos_b]<r[pos_r]){
		sumb+=b[pos_b]-b[0];
		pos_b++;
	}
	return sumr+sumb+max(r.size()-1,b.size()-1)*dist;
}

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