Submission #1184878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184878		hamzabc	Wiring (IOI17_wiring)	C++20	7 / 100	163 ms	327680 KiB

wiring

#include "wiring.h"


#include <bits/stdc++.h>


using namespace std;
std::vector<int> R, B;
vector<pair<int, bool>> C;  // false -> red, true -> blue
std::vector<int> C2O;  // next different color index
vector<vector<long long>> memoiazion;
int A, N, K;  // N -> red, K -> blue


long long dp(int a, int nk, int mk){
	if (a == N + K){
		return 0;
	}
	int combined = nk - mk + K;
	if (memoiazion[a][combined] != -1){
		return memoiazion[a][combined];
	}
	if (C[a].second && mk){
		memoiazion[a][combined] = dp(a + 1, nk, mk - 1);
		return memoiazion[a][combined];
	}
	if (!C[a].second && nk){
		memoiazion[a][combined] = dp(a + 1, nk - 1, mk);
		return memoiazion[a][combined];
	}
	if (C[a].second){
		if (C2O[a] == 0)
			memoiazion[a][combined] = dp(a + 1, nk, mk) + R[C2O[a]] - C[a].first;
		else if (C2O[a] == N)
			memoiazion[a][combined] = dp(a + 1, nk, mk) + C[a].first - R[C2O[a] - 1];
		else
			memoiazion[a][combined] = dp(a + 1, nk, mk) + min(R[C2O[a]] - C[a].first, C[a].first - R[C2O[a] - 1]);
		if (C2O[a] + nk < N){
			memoiazion[a][combined] = min(memoiazion[a][combined], dp(a + 1, nk + 1, mk) + R[C2O[a] + nk] - C[a].first);
		}
		return memoiazion[a][combined];
	}
	if (C2O[a] == 0)
		memoiazion[a][combined] = dp(a + 1, nk, mk) + B[C2O[a]] - C[a].first;
	else if (C2O[a] == K)
		memoiazion[a][combined] = dp(a + 1, nk, mk) + C[a].first - B[C2O[a] - 1];
	else
		memoiazion[a][combined] = dp(a + 1, nk, mk) + min(B[C2O[a]] - C[a].first, C[a].first - B[C2O[a] - 1]);
	if (C2O[a] + mk < K){
		memoiazion[a][combined] = min(memoiazion[a][combined], dp(a + 1, nk, mk + 1) + B[C2O[a] + mk] - C[a].first);
	}
	return memoiazion[a][combined];
}


long long min_total_length(std::vector<int> r, std::vector<int> b) {
	N = r.size();
	K = b.size();
	R.resize(N);
	B.resize(K);
	C2O.resize(N + K);
	C.resize(N + K);
	for (int i = 0; i < N; i++){
		R[i] = r[i];
	}
	for (int i = 0; i < K; i++){
		B[i] = b[i];
	}
	int j = 0;
	for (int i = 0; i < K + N; i++){
		if (j == N){
			C[i].first = B[i - j];
			C[i].second = true;
			C2O[i] = j;
		}else if (i - j == K){
			C[i].first = R[j];
			C[i].second = false;
			C2O[i] = i - j;
			j++;
		}else if (B[i - j] < R[j]){
			C[i].first = B[i - j];
			C[i].second = true;
			C2O[i] = j;
		}else{
			C[i].first = R[j];
			C[i].second = false;
			C2O[i] = i - j;
			j++;
		}
	}
	memoiazion.resize(N + K, vector<long long>(N + K + 1, -1));
	return dp(0, 0, 0);
}

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