제출 #424974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
424974		rainboy	전선 연결 (IOI17_wiring)	C++17	20 / 100	37 ms	3748 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 = 0;

		for (i = 0; i < n; i++)
			ans -= aa[i];
		for (j = 0; j < m; j++)
			ans += bb[j];
		if (n > m)
			ans += (long long) bb[0] * (n - m);
		else
			ans -= (long long) aa[n - 1] * (m - n);
		return ans;
	}
}

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