제출 #1073940

#제출 시각아이디문제언어결과실행 시간메모리
1073940LCJLY전선 연결 (IOI17_wiring)C++14
7 / 100
21 ms5440 KiB
#include <bits/stdc++.h>
#include "wiring.h"
//#include "grader.cpp"
using namespace std;

#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;

int arr[205];
int arr2[205];
int n=0;
int m=0;

int memo[205][205];

int dp(int l, int r){
	if(l==n||r==m){
		if(l==n&&r==m) return 0;
		else return 1e17;
	}
	if(memo[l][r]!=-1) return memo[l][r];
	int ans=1e17;
	ans=min(ans,dp(l+1,r)+abs(arr[l]-arr2[r]));
	ans=min(ans,dp(l,r+1)+abs(arr[l]-arr2[r]));
	ans=min(ans,dp(l+1,r+1)+abs(arr[l]-arr2[r]));
	return memo[l][r]=ans;
}

long long min_total_length(vector<int32_t>r, vector<int32_t>b) {
	n=r.size();
	m=b.size();
	for(int x=0;x<n;x++) arr[x]=r[x];
	for(int x=0;x<m;x++) arr2[x]=b[x];
	memset(memo,-1,sizeof(memo));
	return dp(0,0);
}
#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...