Submission #1209824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209824		repsak	Wiring (IOI17_wiring)	C++20	13 / 100	15 ms	1968 KiB

wiring

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

// Subtask 1)   O(N^3) = +7 points <-- this solution
// Subtask 2)  Trivial = +13 points

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;
}

ll solveN3(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];
}

long long min_total_length(vector<int> r, vector<int> b) {
	// return solveN3(r, b);

	int N = r.size(); int M = b.size();
	int meetingPoint = b[0];
	ll distance = 0;

	for(int i = 0; i < N; i++){
		distance += abs(r[i] - meetingPoint);
	}
	for(int i = 0; i < M; i++){
		distance += abs(b[i] - meetingPoint);
	}

	// Handle cases where:   N != M
	if(M > N){
		for(int i = N; i < M; i++){
			distance += abs(meetingPoint - r[N - 1]);
		}
	}

	return distance;
}

// #include "grader.cpp"

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