Submission #69932

#	Time	Username	Problem	Language	Result	Execution time	Memory
69932		E869120	Wiring (IOI17_wiring)	C++14	7 / 100	1083 ms	10416 KiB

wiring

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

int R[100009], B[100009], r[100009], b[100009], N, M; vector<int>X[100009];
long long dp[200009];

long long total_sum(long long px, long long py, long long qx, long long qy){
	long long ret = 0, cy = py;
	for(int i=px;i<=qx;i++){
		ret += abs(R[i] - B[cy]);cy++;
	}
	return ret;
}

void init(){
	for(int i=0;i<N;i++){
		int pos1=lower_bound(B,B+M,R[i])-B;
		int minx=(1<<30),minid=-10;
		if(pos1<M){int z=abs(R[i]-B[pos1]);if(z<minx){minx=z;minid=pos1;}}
		if(pos1>0){int z=abs(R[i]-B[pos1-1]);if(z<minx){minx=z;minid=pos1-1;}}
		X[i].push_back(minid);
	}
	for(int i=0;i<M;i++){
		int pos1=lower_bound(R,R+N,B[i])-R;
		int minx=(1<<30),minid=-10;
		if(pos1<N){int z=abs(B[i]-R[pos1]);if(z<minx){minx=z;minid=pos1;}}
		if(pos1>0){int z=abs(B[i]-R[pos1-1]);if(z<minx){minx=z;minid=pos1-1;}}
		X[minid].push_back(i);
	}
}

long long getval(long long cx,long long cy){
	if(cx<=0 || cy<=0) return (1LL<<60);
	long long E1 = cy - cx + N;
	long long ex = 0, ey = 0; if(cx > cy) ex = cx - cy; if(cx < cy) ey = cy - cx;
	long long vx = total_sum(ex, ey, cx - 1, cy - 1) + dp[E1];
	return vx;
}
void writeval(long long cx,long long cy,long long t){
	long long E1 = cy - cx + N;
	long long ex = 0, ey = 0; if(cx > cy) ex = cx - cy; if(cx < cy) ey = cy - cx;
	long long F = total_sum(ex, ey, cx - 1, cy - 1);
	dp[E1] = min(dp[E1], t - F);
}

long long min_total_length(vector<int> r, vector<int> b) {
	// -------------------------- 第一部：前準備 --------------------------
	N = r.size(); for(int i=0;i<N;i++) R[i] = r[i];
	M = b.size(); for(int i=0;i<M;i++) B[i] = b[i];
	
	init();
	for(int i=0;i<=N+M;i++) dp[i] = (1LL<<60);
	for(int i=0;i<N;i++) sort(X[i].begin(),X[i].end());
	
	dp[N]=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<(int)X[i].size();j++){
			long long v0 = getval(i+1,X[i][j]+1);
			long long v1 = getval(i+1,X[i][j]); if(v1!=(1LL<<60))v1+=abs(R[i]-B[X[i][j]]);
			long long v2 = getval(i, X[i][j]+1); if(v2!=(1LL<<60))v2+=abs(R[i]-B[X[i][j]]);
			writeval(i+1,X[i][j]+1,min({v0,v1,v2}));
			//cout<<i<<" "<<X[i][j]<<" "<<v0<<" "<<v1<<" "<<v2<<endl;
		}
		//for(int i=0;i<=N+M;i++) cout<<i<<":"<<dp[i]<<endl;
	}
	return getval(N, M);
}

/*int main(){
	int n,m;cin>>n>>m;
	vector<int>vec1,vec2;
	for(int i=0;i<n;i++){int p;cin>>p;vec1.push_back(p);}
	for(int i=0;i<m;i++){int p;cin>>p;vec2.push_back(p);}
	
	cout<<min_total_length(vec1,vec2)<<endl;
	return 0;
}*/

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