Submission #301676

#	Time	Username	Problem	Language	Result	Execution time	Memory
301676		TMJN	Wiring (IOI17_wiring)	C++17	0 / 100	13 ms	12416 KiB

wiring

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

long long DP[400][210][210];
int N;

vector<pair<long long,bool>>V;

long long min_total_length(vector<int>r,vector<int>b){
	for(int i:r){
		V.push_back({i,0});
	}
	for(int i:b){
		V.push_back({i,1});
	}
	N=V.size();
	sort(V.begin(),V.end());
	for(int i=0;i<N;i++){
		for(int j=0;j<210;j++){
			for(int k=0;k<210;k++){
				DP[i][j][k]=0xE869120E869120;
			}
		}
	}
	for(int i=1;i<=200;i++){
		if(V[0].second){
			DP[0][0][i]=0;
		}
		else{
			DP[0][i][0]=0;
		}
	}
	for(int i=1;i<N;i++){
		for(int j=0;j<=200;j++){
			for(int k=0;k<=200;k++){
				if(V[i].second){
					DP[i][j][k]=min({DP[i-1][j+1][k]+(j+1+k)*(V[i].first-V[i-1].first),(j?DP[i-1][j][k]+(j+k)*(V[i].first-V[i-1].first):0xE869120E869120),(k?DP[i][j][k-1]:0xE869120E869120)});
				}
				else{
					DP[i][j][k]=min({DP[i-1][j][k+1]+(j+1+k)*(V[i].first-V[i-1].first),(k?DP[i-1][j][k]+(j+k)*(V[i].first-V[i-1].first):0xE869120E869120),(j?DP[i][j-1][k]:0xE869120E869120)});
				}
			}
		}
	}
	return DP[N-1][0][0];
}

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