제출 #301884

#제출 시각아이디문제언어결과실행 시간메모리
301884lakshith_전선 연결 (IOI17_wiring)C++14
13 / 100
42 ms4728 KiB
#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long

const ll INF = LLONG_MAX - 1e17; 

using namespace std;

vector<int> r;
vector<int> b;

ll dp[500][500];

ll solve(int i,int j){
	if(i==0 && j==0)return abs(r[0]-b[0]);
	else if(i<0 || j<0)return INF;
	if(dp[i][j]!=0)return dp[i][j];
	dp[i][j] = min(solve(i-1,j),min(solve(i,j-1),solve(i-1,j-1))) + abs(r[i]-b[j]);
	return dp[i][j];
}

long long min_total_length(std::vector<int> R, std::vector<int> B){
	r=R,b=B;
	//subtask 1
	// return solve(R.size()-1,B.size()-1);
	ll ans = 0;
	for(int x:R)
		ans += abs(x-R[R.size()-1]);
	for(int x:B)
		ans += abs(x-B[0]);
	ans += max(R.size(),B.size())*abs(R[R.size()-1]-B[0]);
	return ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...