Submission #1285638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285638		WH8	전선 연결 (IOI17_wiring)	C++20	55 / 100	42 ms	10520 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[0]=0;
	for(int j=0;j<(int)v[0].size();j++){
		p[0]+=v[0].back()-v[0][j];
	}
	pw[0]=p[0] + v[0].size() * (v[1][0]-v[0].back());
	for(int i=1;i<=(int)v[0].size();i++){
		pw[i]=min(pw[i-1], p[i]+((int)v[0].size()-i+1)*(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.back()+tr;
		//~ 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(
				((int)v[i-1].size()-j+1 >= 0 ? p[v[i-1].size()-j+1] : p[0])+j*a+tr+tl,
				((int)v[i-1].size()-j >= 0 ? pw[v[i-1].size()-j]: (ll)1e15)+tr+tl
			);
		}		
		//~ printf("%d, dp values before cleaning: \n", i);
		//~ for(auto it : cur)cout<<it<<" ";
		//~ cout<<endl;
		
		swap(cur, p);
		//~ printf("i is %d, size is %d\n", i, (int)v[i].size());
		for(int j=0;j<(int)v[i].size();j++){
			//~ cout<<p[j]<<" "<<p[j+1]<<'\n';;
			p[j]=min(p[j+1],p[j]);
		}
		vector<ll> npw(p.begin(),p.end());
				//~ printf("%d, dp values after cleaning: \n", i);
		//~ for(auto it : p)cout<<it<<" ";
		//~ cout<<endl;
		
		//~ for(auto it: npw)cout<<it<<' ';
		//~ cout<<endl;
		int na=(i==(int)v.size()-1? 0: v[i+1][0]-v[i].back());
		npw[0]+=v[i].size() * na;
		for(int j=1;j<=(int)v[i].size();j++){
			npw[j]=min(npw[j-1], p[j]+((int)v[i].size()-j)*na);
		}
		for(int j=(int)v[i].size()-1;j>=0;j--){
			p[j]=min(p[j+1], p[j]);
		}

		swap(npw, pw);
	}
	return p.back();
}
/*
4 2 
1 2 9 12
4 7

4 5
1 2 3 7
0 4 5 9 10

1 4
5
1 2 7 8

5 3
0 1 3 100 500 
2 4 6

*/

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