제출 #282447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282447		MohamedAhmed04	전선 연결 (IOI17_wiring)	C++14	7 / 100	37 ms	5368 KiB

wiring

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

using namespace std ;

const int MAX = 210 ;

long long dp[MAX][MAX][2] ;
int n , m ;
vector<int>A , B ;

long long solve(int idx , int idx2 , bool flag)
{
	if(idx == n)
	{
		if(idx2 != m)
			return 1e18 ;
		else
			return 0 ;
	}
	long long &ret = dp[idx][idx2][flag] ;
	if(ret != -1)
		return ret ;
	ret = 1e18 ;
	if(flag)
		ret = solve(idx+1 , idx2 , 0) ;
	if(idx2 != m)
		ret = min(ret , solve(idx , idx2 + 1 , 1) + abs(A[idx] - B[idx2])) ;
	if(idx2 != 0)
		ret = min(ret , solve(idx , idx2 , 1) + abs(A[idx] - B[idx2-1])) ;
	return ret ;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) 
{
	memset(dp , -1 , sizeof(dp)) ;
	A = r , B = b ;
	n = A.size() , m = B.size() ;
	return solve(0 , 0 , 0) ;
}

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