Submission #895637

#	Time	Username	Problem	Language	Result	Execution time	Memory
895637		joonwu04	Wiring (IOI17_wiring)	C++17	7 / 100	19 ms	3928 KiB

wiring

#include "wiring.h" 
#include <iostream>
#define MAX 1000000000000

using namespace std;

typedef long long ll;

ll sub1Dp[210][210]; // sub1Dp[i][j]: minCost when connecting r[0~i], b[0~j]

ll abs(ll x) {
	return x>=0 ? x:-x;
}

ll isSub1(int rSize, int bSize) {
	return rSize<=200 && bSize<=200;
}

ll sub1(vector<int> &r, vector<int> &b) {
	int n = r.size(), m = b.size();
	
	sub1Dp[0][0] = abs(r[0] - b[0]);
	for(int j=1; j<m; j++) {
		sub1Dp[0][j] = sub1Dp[0][j-1] + abs(r[0] - b[j]);
	}
	for(int i=1; i<n; i++) {
		sub1Dp[i][0] = sub1Dp[i-1][0] + abs(r[i] - b[0]);
		for(int j=1; j<m; j++) {
			// r[i], b[j] should be connected
			ll connectingCost = abs(r[i] - b[j]);
			
			// case 1: r[i], b[j] are seperated to the rest
			ll t = sub1Dp[i-1][j-1]; // t is the restCost	
			
			// case 2: r[i] is connected to the rest 
			// in this case, b[j] is seperated to the rest
			t = min(t, sub1Dp[i][j-1]);
			
			// case 3: b[j] is connected to the rest
			// in this case, r[i] is seperated to the rest
			t = min(t, sub1Dp[i-1][j]);
			
			sub1Dp[i][j] = t + connectingCost;
		}
	}
	
	return sub1Dp[n-1][m-1];
}

ll min_total_length(vector<int> r, vector<int> b) {
	int n = r.size(), m = b.size();
	if(isSub1(n, m)) {
		return sub1(r, b);
	}
	else return 0;
}

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