Submission #1184927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184927		hamzabc	Wiring (IOI17_wiring)	C++20	13 / 100	27 ms	17480 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
std::vector<int> C2N;  // current color index
vector<int> B2C, R2C;
vector<long long> Cclose;
long long *prefixCclose;
vector<long long> memoiazion;
int A, N, K;  // N -> red, K -> blue


long long dp(int a){
	if (a >= N + K){
		return 0;
	}
	if (memoiazion[a] != -1){
		return memoiazion[a];
	}
	if (C[a].second){
		memoiazion[a] = prefixCclose[N + K - 1] - prefixCclose[a - 1];
		long long int add = 0;
		for (int i = C2O[a], j = C2N[a]; i < N && j < K; i++, j++){
			add += -Cclose[B2C[j]] - Cclose[R2C[i]] + abs(C[R2C[i]].first - C[B2C[j]].first);
			if (memoiazion[a] < dp(max(R2C[i], B2C[j]) + 1) + prefixCclose[max(R2C[i], B2C[j])] - prefixCclose[a - 1] + add)
				break;
			memoiazion[a] = dp(max(R2C[i], B2C[j]) + 1) + prefixCclose[max(R2C[i], B2C[j])] - prefixCclose[a - 1] + add;
		}
		return memoiazion[a];
	}
	memoiazion[a] = prefixCclose[N + K - 1] - prefixCclose[a - 1];
	long long int add = 0;
	for (int i = C2O[a], j = C2N[a]; i < K && j < N; i++, j++){
		add += -Cclose[R2C[j]] - Cclose[B2C[i]] + abs(C[B2C[i]].first - C[R2C[j]].first);
		if (memoiazion[a] < dp(max(B2C[i], R2C[j]) + 1) + prefixCclose[max(B2C[i], R2C[j])] - prefixCclose[a - 1] + add)
			break;
		memoiazion[a] = dp(max(B2C[i], R2C[j]) + 1) + prefixCclose[max(B2C[i], R2C[j])] - prefixCclose[a - 1] + add;
	}
	return memoiazion[a];
}


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);
	R2C.resize(N);
	B2C.resize(K);
	C2O.resize(N + K);
	C2N.resize(N + K);
	C.resize(N + K);
	Cclose.resize(N + K);
	prefixCclose = new long long[N + K + 1];
	prefixCclose[0] = 0;
	prefixCclose++;  // index -1 = 0
	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];
			B2C[i - j] = i;
			C[i].second = true;
			C2O[i] = j;
			C2N[i] = i - j;
		}else if (i - j == K){
			C[i].first = R[j];
			R2C[j] = i;
			C[i].second = false;
			C2O[i] = i - j;
			C2N[i] = j;
			j++;
		}else if (B[i - j] < R[j]){
			C[i].first = B[i - j];
			B2C[i - j] = i;
			C[i].second = true;
			C2O[i] = j;
			C2N[i] = i - j;
		}else{
			C[i].first = R[j];
			R2C[j] = i;
			C[i].second = false;
			C2O[i] = i - j;
			C2N[i] = j;
			j++;
		}
	}
	for (int i = 0; i < N + K; i++){
		if (C[i].second){
			if (C2O[i] == 0)
				Cclose[i] = R[C2O[i]] - C[i].first;
			else if (C2O[i] == N)
				Cclose[i] = C[i].first - R[C2O[i] - 1];
			else
				Cclose[i] = min(R[C2O[i]] - C[i].first, C[i].first - R[C2O[i] - 1]);
		}else{
			if (C2O[i] == 0)
				Cclose[i] = B[C2O[i]] - C[i].first;
			else if (C2O[i] == K)
				Cclose[i] = C[i].first - B[C2O[i] - 1];
			else
				Cclose[i] = min(B[C2O[i]] - C[i].first, C[i].first - B[C2O[i] - 1]);
		}
	}
	for (int i = 0; i < N + K; i++){
		prefixCclose[i] = prefixCclose[i - 1] + Cclose[i];
	}
	memoiazion.resize(N + K, -1);
	return dp(0);
}

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