Submission #431196

#	Time	Username	Problem	Language	Result	Execution time	Memory
431196		rainboy	Wiring (IOI17_wiring)	C++98	100 / 100	41 ms	4992 KiB

wiring

/* https://codeforces.com/blog/entry/53550?#comment-375680 (majk) */
#include "wiring.h"
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 100000, M = 100000;

long long min(long long a, long long b) { return a < b ? a : b; }

int xx[N + M], cc[N + M];
long long dp[N + M + 1];

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

	i = 0, j = 0, k = 0;
	while (i < n || j < m)
		if (i < n && (j == m || aa[i] < bb[j]))
			xx[k] = aa[i++], cc[k] = 0, k++;
		else
			xx[k] = bb[j++], cc[k] = 1, k++;
	n += m;
	memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = 0;
	for (p = 0, i = 0; i < n; p = i, i = j) {
		long long x;

		j = i + 1;
		while (j < n && cc[j] == cc[i])
			j++;
		for (h = p; h <= i; h++)
			dp[h] = min(dp[h], dp[h - 1] + xx[i] - xx[h - 1]);
		x = 0;
		for (h = i + 1; h <= j && i * 2 - h >= p; h++) {
			x += xx[h - 1] - xx[i * 2 - h];
			dp[h] = dp[i * 2 - h] + x;
		}
		if (i > 0)
			for (h = i + 1; h <= j; h++)
				dp[h] = min(dp[h], dp[h - 1] + xx[h - 1] - xx[i - 1]);
	}
	return dp[n];
}

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