Submission #1209812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209812		repsak	Wiring (IOI17_wiring)	C++20	7 / 100	186 ms	327680 KiB

wiring

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

ll findSmall(vector<int> r, vector<int> b, int isRed, int index, int maxIndex){
	if(!isRed) swap(r, b);

	ll minDist = 1e9;
	for(int i = 0; i < b.size(); i++){
		int bVal = b[i];

		if(i > maxIndex) return minDist;

		minDist = min(
			minDist,
			ll(abs(r[index] - bVal))
		);
	}

	return minDist;
}

long long min_total_length(vector<int> r, vector<int> b) {
	ll MAX = 1e18;
	int M = b.size(); int N = r.size();
	vector<vector<ll>> dp(M, vector<ll>(N, MAX));

	dp[0][0] = abs(b[0] - r[0]);

	for(int m = 0; m < M; m++){
		for(int n = 0; n < N; n++){
			if(m == 0 && n == 0) continue;
			if(n == 0){
				dp[m][n] = dp[m - 1][n] + abs(b[m] - r[0]);
				continue;
			}
			if(m == 0){
				dp[m][n] = dp[m][n - 1] + abs(b[m] - r[n]);
				continue;
			}

			dp[m][n] = min({
				dp[m][n - 1] + findSmall(r, b, true, n, m),
				dp[m - 1][n - 1] + abs(b[m] - r[n]),
				dp[m - 1][n] + findSmall(r, b, false, m, n)
			});
		}
	}

	return dp[M - 1][N - 1];
}

// #include "grader.cpp"

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