Submission #1145331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145331		SmuggingSpun	Wiring (IOI17_wiring)	C++20	0 / 100	0 ms	328 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const ll INF = 1e18;
ll min_total_length(vector<int>r, vector<int>b){
	ll ans = 0;
	int n = r.size(), m = b.size();
	if(n <= 200 && m <= 200){
		vector<vector<ll>>dp(n + 1, vector<ll>(m + 1, INF));
		dp[n][m] = dp[n][m - 1] = dp[n - 1][m] = 0;
		for(int i = n - 1; i > -1; i--){
			for(int j = m - 1; j > -1; j--){
				dp[i][j] = dp[i + 1][j + 1] + abs(r[i] - b[j]);
				for(int k = n - 1; k > i; k--){
					minimize(dp[i][j], dp[i][j + 1] + abs(r[k] - b[j]));
				}	
				for(int k = m - 1; k > j; k--){
					minimize(dp[i][j], dp[i + 1][j] + abs(r[i] - b[k]));
				}
			}
		}
		return dp[0][0];
	}
	else if(r.back() < b[0]){
		int i = r.size(), j = b.size();
		while(i > 0 && j > 0){
			ans += b[--j] - r[--i];
		}
		while(i > 0){
			ans += b[0] - r[--i];
		}
		while(j > 0){
			ans += b[--j] - r.back();
		}
	}
	return ans;
}

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