Submission #425061

#	Time	Username	Problem	Language	Result	Execution time	Memory
425061		rainboy	Wiring (IOI17_wiring)	C++17	0 / 100	0 ms	204 KiB

wiring

#include "wiring.h"
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 100000, M = 100000;
const int SMALL = 200;

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[M + N + 1];

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

	if (n <= SMALL && m <= SMALL) {
		memset(dp, 0, n * sizeof *dp), i = 0, j = 0, o = n, x = min(aa[0], bb[0]);
		while (i < n || j < m)
			if (i < n && (j == m || aa[i] < bb[j])) {
				for (k = 0; k <= n + m; k++)
					dp[k] += (long long) (aa[i] - x) * abs_(k - o);
				x = aa[i];
				i++, o--;
				for (k = 1; k <= n + m; k++)
					dp[k] = min(dp[k], dp[k - 1]);
			} else {
				for (k = 0; k <= n + m; k++)
					dp[k] += (long long) (bb[j] - x) * abs_(k - o);
				x = bb[j];
				j++, o++;
				for (k = n + m - 1; k >= 0; k--)
					dp[k] = min(dp[k], dp[k + 1]);
			}
		return dp[o];
	} 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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45