Submission #1184940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184940		hamzabc	전선 연결 (IOI17_wiring)	C++20	0 / 100	1102 ms	195704 KiB

wiring

#include "wiring.h"


#include <bits/stdc++.h>


using namespace std;
int Nr, Nb;
std::vector<long long> R;
std::vector<long long> B;
std::vector<long long> Bclose;
std::vector<long long> Rclose;
vector<map<long long, int>> mem;


long long int dp(int r, int b){
	if (r == Nr && b == Nb){
		return 0;
	}
	if (mem[r][b])
		return mem[r][b];
	if (r == Nr){
		mem[r][b] = dp(r, b + 1) + Bclose[b];
		return mem[r][b];
	}
	if (b == Nb){
		mem[r][b] = dp(r + 1, b) + Bclose[r];
		return mem[r][b];
	}
	if (R[r] < B[b]){
		mem[r][b] = min(dp(r + 1, b + 1) + B[b] - R[r], dp(r + 1, b) + Rclose[r]);
	}else{
		mem[r][b] = min(dp(r + 1, b + 1) + R[r] - B[b], dp(r, b + 1) + Bclose[b]);
	}
	return mem[r][b];
}



long long min_total_length(std::vector<int> r, std::vector<int> b) {
	Nr = r.size();
	Nb = b.size();
	R.resize(Nr);
	B.resize(Nb);
	Rclose.resize(Nr);
	Bclose.resize(Nb);
	int j = 0;
	for (int i = 0; i < Nr; i++){
		R[i] = r[i];
	}
	for (int i = 0; i < Nb; i++){
		B[i] = b[i];
	}
	for (int i = 0; i < Nr + Nb; i++){
		if ((i - j != Nr) && (j == Nb || r[i - j] < b[j])){
			if (j && j < Nb){
				Rclose[i - j] = min(b[j] - r[i - j], r[i - j] - b[j - 1]);
			}else if (j){
				Rclose[i - j] = r[i - j] - b[j - 1];
			}else{
				Rclose[i - j] = b[j] - r[i - j];
			}
		}else{
			if (i - j && i - j < Nr){
				Bclose[j] = min(r[i - j] - b[j], b[j] - r[i - j - 1]);
			}else if (i - j){
				Bclose[j] = b[j] - r[i - j - 1];
			}else{
				Bclose[j] = r[i - j] - b[j];
			}
			j++;
		}
	}
	mem.resize(Nr + 1);
	return dp(0, 0);
}

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