Submission #826949

#	Time	Username	Problem	Language	Result	Execution time	Memory
826949		tranxuanbach	Wiring (IOI17_wiring)	C++17	7 / 100	98 ms	262144 KiB

wiring

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

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())

using ll = long long;

const ll infll = (ll)1e18 + 7;

ll min_total_length(vector <int> r, vector <int> b){
	int n = isz(r), m = isz(b);

	vector <vector <ll>> dp(n + 1, vector <ll>(m + 1, infll));
	dp[0][0] = 0;
	ForE(i, 0, n){
		ForE(j, 0, m){
			if (i < n and j > 0){
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + abs(r[i] - b[j - 1]));
			}
			if (i > 0 and j < m){
				dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + abs(r[i - 1] - b[j]));
			}
			if (i < n and j < m){
				dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(r[i] - b[j]));
			}
		}
	}
	return dp[n][m];
}

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