Submission #301818

#	Time	Username	Problem	Language	Result	Execution time	Memory
301818		TMJN	Wiring (IOI17_wiring)	C++17	10 / 100	377 ms	215256 KiB

wiring

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

long long min_total_length(vector<int>r,vector<int>b){
	vector<pair<long long,bool>>V;
	for(int i:r){
		V.push_back({i,0});
	}
	for(int i:b){
		V.push_back({i,1});
	}
	sort(V.begin(),V.end());
	long long l[2];
	int N=V.size();
	l[0]=l[1]=-0xE869120E869120;
	vector<vector<long long>>DP(N+1,vector<long long>(1<<7,0xE869120E869120));
	for(int i=0;i<10;i++){
		V.push_back({0xE869120E869120,i&1});
	}
	DP[0][0]=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<(1<<7);j++){
			if(j&1){
				DP[i+1][j/2]=min(DP[i+1][j/2],DP[i][j]);
			}
			else{
				DP[i+1][j/2]=min(DP[i+1][j/2],DP[i][j]+V[i].first-l[!V[i].second]);
				for(int k=1;k<7;k++){
					if(V[i].second!=V[i+k].second){
						int t=(j|(1<<k));
						t/=2;
						DP[i+1][t]=min(DP[i+1][t],DP[i][j]+V[i+k].first-V[i].first);
					}
				}
			}
		}
		l[V[i].second]=V[i].first;
	}
	return DP[N][0];
}

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