제출 #598021

#제출 시각아이디문제언어결과실행 시간메모리
598021Lucpp전선 연결 (IOI17_wiring)C++17
7 / 100
1087 ms5324 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; ll min_total_length(vector<int> r, vector<int> b) { int n = int(r.size()), m = int(b.size()); vector<ll> dp(m+1, INF); dp[0] = 0; for(int i = 0; i < n; i++){ vector<ll> dp2(m+1, INF); for(int j = 1; j <= m; j++){ dp2[j] = min(dp2[j], dp[j]+abs(b[j-1]-r[i])); ll cost = 0; for(int k = j-1; k >= 0; k--){ cost += abs(b[k]-r[i]); dp2[j] = min(dp2[j], dp[k]+cost); } // cerr << i << " " << j << " " << dp2[j] << "\n"; } dp = dp2; } return dp[m]; }
#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...