제출 #299586

#제출 시각아이디문제언어결과실행 시간메모리
299586infinite_iq전선 연결 (IOI17_wiring)C++14
7 / 100
59 ms7800 KiB
#include <bits/stdc++.h> using namespace std ; #define pb push_back #define fi first #define se second typedef long long ll ; typedef vector < int > vi ; typedef pair < int , int > pi ; typedef vector < pi > vpi ; #include "wiring.h" int n , m ; vi a , b ; ll dp [209][209] ; ll bt ( int i , int j ) { if ( i == n && j == m ) return 0ll ; if ( i == n || j == m ) return 1e18 ; ll &ret = dp [i][j] ; if ( ret != -1 ) return ret ; ret = 1e18 ; ll cost = 0 ; for ( ll nxt = j ; nxt < m ; nxt ++ ) { cost += abs ( a [i] - b [nxt] ) ; ret = min ( ret , bt ( i + 1 , nxt + 1 ) + cost ) ; } cost = 0 ; for ( ll nxt = i ; nxt < n ; nxt ++ ) { cost += abs ( a [nxt] - b [j] ) ; ret = min ( ret , bt ( nxt + 1 , j + 1 ) + cost ) ; } return ret ; } long long min_total_length ( vi A , vi B ) { memset ( dp , -1 , sizeof (dp) ) ; if ( A .size () > B .size () ) swap ( A , B ) ; n = A .size () , m = B .size () ; a = A , b = B ; return bt ( 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...