제출 #410544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410544		dreezy	전선 연결 (IOI17_wiring)	C++17	7 / 100	157 ms	262148 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define pb push_back


ll min_total_length(vector<int> r, vector<int> b){
	//for each point calculate the closest one
	//pair all the closest ones firs	
	
	
	int n = r.size();
	int m = b.size();
	vector<vector<ll>> dp(n, vector<ll>(m,0));
	ll sumr = 0, sumb = 0;
	for(int i =0; i< n; i++){
		sumr +=abs(r[i]- b[0]);
		dp[i][0] = sumr;
	}	
	
	for(int i =0; i< m; i++){
		sumb +=abs(r[0]- b[i]);
		dp[0][i] = sumb;
	}	
	
	for(int i =1; i< n; i++){
		for(int j =1; j< m; j++){
			dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }) + abs(r[i] - b[j]);
		}
	}
	
	
	
	return dp[n-1][m-1];
}

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