Submission #424969

#	Time	Username	Problem	Language	Result	Execution time	Memory
424969		rainboy	전선 연결 (IOI17_wiring)	C++17	7 / 100	1079 ms	2192 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;

	if (n <= SMALL && m <= SMALL) {
		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];
	} else {
		long long ans;

		i = 0, j = m - 1, ans = 0;
		while (i < n || j >= 0) {
			ans += bb[j] - aa[i];
			if (i + 1 < n)
				i++;
			if (j > 0)
				j--;
		}
		return ans;
	}
}

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