제출 #559548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559548		jamezzz	전선 연결 (IOI17_wiring)	C++17	0 / 100	1087 ms	136912 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define maxn 100005

int n,m,cnt[maxn];
vector<int> r,b;
deque<int> dq[maxn];

ll min_total_length(vector<int> _r,vector<int> _b){
	r=_r;b=_b;
	n=r.size(),m=b.size();
	if(n>m)swap(n,m),swap(r,b);
	int cur=0;
	for(int i=0;i<m;++i){
		while(cur!=n-1&&abs(b[i]-r[cur+1])<abs(b[i]-r[cur]))++cur;
		dq[cur].push_back(i);
	}
	for(int i=n-1;i>=0;--i){
		cnt[i]=cnt[i+1]+dq[i].size();
	}
	ll ans=0;
	for(int i=0;i<n;++i){
		if(dq[i].empty()){
			dq[i].push_back(dq[i+1].front());
			dq[i+1].pop_front();
		}
		else{
			for(int j=0;j<n-i-1-cnt[i+1];++j){
				dq[i+1].push_front(dq[i].back());
				dq[i].pop_back();
			}
		}
		for(int j:dq[i]){
			ans+=abs(r[i]-b[j]);
		}
	}
	return ans;
}

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