Submission #425082

#	Time	Username	Problem	Language	Result	Execution time	Memory
425082		rainboy	Wiring (IOI17_wiring)	C++17	20 / 100	51 ms	3696 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;
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[N + M + 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, 0x3f, (n + m + 1) * sizeof *dp), dp[n] = 0;
		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++)
					if (dp[k] != INF)
						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++)
					if (dp[k] != INF)
						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: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45