제출 #1285344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285344		WH8	전선 연결 (IOI17_wiring)	C++20	13 / 100	42 ms	10524 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define s second
#define f first
typedef long long ll;

ll min_total_length(vector<int> R, vector<int> B) {
	const int n=R.size(),m=B.size();
	vector<pair<ll,int>> pos;
	for(auto it : R ){
		pos.push_back({it, 0});
	}
	for(auto it: B){
		pos.push_back({it, 1});
	}
	sort(pos.begin(),pos.end());
	vector<vector<ll>> v={{pos[0].f}};
	for(int i=1;i<n+m;i++){
		if(pos[i].s==pos[i-1].s){
			v.back().push_back(pos[i].f);
		}
		else {
			v.push_back({pos[i].f});
		}
	}
	
	vector<ll> p(v[0].size()+1, 1e15), pw(v[0].size()+1, 1e15);
	p[v[0].size()]=0;
	for(int j=0;j<(int)v[0].size();j++){
		p[v[0].size()]+=v[0].back()-v[0][j];
	}
	pw[v[0].size()]=p[v[0].size()] + v[0].size() * (v[1][0]-v[0].back());
	for(int i=v[0].size()-1;i>=0;i--){
		pw[i]=min(pw[i+1], p[i]+i*(v[1][0]-v[0].back()));
	}
	//~ for(int i=0;i<(int)v.size();i++){
		//~ cout<<"vector " << i <<" : ";
		//~ for(auto it:v[i])cout<<it<<' ';
		//~ cout<<endl;
	//~ }
	//~ for(auto it:p)cout<<it<<" ";
	//~ cout<<endl;
	//~ for(auto it:pw) cout<<it<<" ";
	//~ cout<<endl;
	//~ cout<<endl;

	for(int i=1;i<(int)v.size();i++){

		vector<ll> cur(v[i].size()+1, 1e15);
		ll tr=0, tl=0,a=v[i][0]-v[i-1].back();
		for(int j=0;j<(int)v[i].size();j++) tr+=v[i].back()-v[i][j];
		cur[0]=p[0];
		//~ cout<<i<<endl;
		for(int j=1;j<=(int)v[i].size();j++){
			tr-=(v[i].back()-v[i][j-1]);
			tl+=(v[i][j-1] - v[i][0]);
			cur[j]=min(
				(j >= (int)p.size() ? p.back() : p[j])+j*a+tr+tl,
				(j >= (int)pw.size() ? (ll)1e15 : pw[j]+tr)+tl
			);
		}
		reverse(cur.begin(),cur.end());
		
		//~ for(auto it : cur)cout<<it<<" ";
		//~ cout<<endl;
		
		swap(cur, p);
		if(v[i].size()==1) p[1]=min(p[0],p[1]),p[0]=min(p[0],p[1]);
		
		vector<ll> npw(p.begin(),p.end());
		//~ for(auto it: npw)cout<<it<<' ';
		//~ cout<<endl;
		int na=(i==(int)v.size()-1? 0: v[i+1][0]-v[i].back());
		npw[v[i].size()]+=v[i].size() * na;
		for(int j=(int)v[i].size()-1;j>=0;j--){
			npw[j]=min(npw[j+1], p[j]+j*na);
		}
		for(int j=2;j<=(int)v[i].size();j++){
			p[j]=min(p[j-1], p[j]);
		}
		swap(npw, pw);
	}
	return p[0];
}
/*
4 5
1 2 3 7
0 4 5 9 10

1 4
5
1 2 7 8

*/

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