Submission #301699

#	Time	Username	Problem	Language	Result	Execution time	Memory
301699		TMJN	Wiring (IOI17_wiring)	C++17	0 / 100	46 ms	11992 KiB

wiring

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

long long DP[400][210][2];
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<2;k++){
				DP[i][j][k]=0xE869120E869120;
			}
		}
	}
	for(int i=1;i<=200;i++){
		DP[0][i][V[0].second]=0;
	}
	for(int i=1;i<N;i++){
		DP[i-1][0][0]=DP[i-1][0][1]=min(DP[i-1][0][0],DP[i-1][0][1]);
		for(int j=200;j>=0;j--){
			DP[i][j][!V[i].second]=min(DP[i][j+1][!V[i].second],DP[i-1][j+1][!V[i].second]+(j+1)*(V[i].first-V[i-1].first));
		}
		DP[i][0][V[i].second]=DP[i][0][!V[i].second];
		for(int j=0;j<=200;j++){
			DP[i][j][V[i].second]=min(DP[i][0][V[i].second],(j?DP[i-1][j-1][V[i].second]+(j-1)*(V[i].first-V[i-1].first):0xE869120E869120));
		}

	}
	return min(DP[N-1][0][0],DP[N-1][0][1]);
}

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