제출 #895633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895633		joonwu04	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	348 KiB

wiring

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

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();
	
	for(int i=0; i<n; i++) {
		for(int j=0; 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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45