Submission #424957

#	Time	Username	Problem	Language	Result	Execution time	Memory
424957		rainboy	Wiring (IOI17_wiring)	C++17	7 / 100	37 ms	6092 KiB

wiring

#include "wiring.h"

using namespace std;

typedef vector<int> vi;

const int SMALL = 200;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int abs_(int x) { return x > 0 ? x : -x; }
long long min(long long a, long long b) { return a < b ? a : b; }

long long dp[SMALL][SMALL];

long long min_total_length(vi aa, vi bb) {
	int n = aa.size(), m = bb.size(), i, j;

	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			if (i == 0 && j == 0)
				dp[i][j] = 0;
			else {
				dp[i][j] = INF;
				if (i > 0)
					dp[i][j] = min(dp[i][j], dp[i - 1][j]);
				if (j > 0)
					dp[i][j] = min(dp[i][j], dp[i][j - 1]);
				if (i > 0 && j > 0)
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
			}
			dp[i][j] += abs_(aa[i] - bb[j]);
		}
	return dp[n - 1][m - 1];
}

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