Submission #78038

#	Time	Username	Problem	Language	Result	Execution time	Memory
78038		shoemakerjo	Wiring (IOI17_wiring)	C++14	7 / 100	1074 ms	8740 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;
#define prev previousguy
#define ll long long
#define maxn 100010

ll dp[2][maxn];

int prev, cur;
int n, m;
const ll inf = 1LL << 62;

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size();
	m = b.size();

	cur = 0; prev = 1;
	//dp j means that j has been taken care of
	for (int i = 0; i < maxn; i++) {
		dp[0][i] = dp[1][i] = inf;
	}
	dp[0][0] = dp[1][0] = 0;
	for (int i = 0; i < n; i++) {
		swap(cur, prev);
		for (int j = 0; j < m; j++) {
			dp[cur][j] = dp[prev][j] + abs(r[i] - b[j]);
			if (j > 0) {
				dp[cur][j] = min(dp[cur][j], 
					dp[cur][j-1] + abs(r[i] - b[j]));
				if (i > 0) dp[cur][j] = min(dp[cur][j],
					dp[prev][j-1] + abs(r[i] - b[j]));
			}

		}
		// cout << i << endl;
		// cout << "     ";
		// for (int j = 0; j < m; j++) {
		// 	cout << dp[cur][j] << " " ;
		// }
		// cout << endl;
	}

	return dp[cur][m-1];
}

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