제출 #40181

#제출 시각아이디문제언어결과실행 시간메모리
40181leejseo전선 연결 (IOI17_wiring)C++98
13 / 100
45 ms3504 KiB
#include "wiring.h" long long abs (long long x){ if (x > 0) return x; return -x; } long long max (long long a, long long b){ if (a > b) return a; return b; } long long min (long long a, long long b){ if (a > b) return b; return a; } long long min_total_length(std::vector<int> r, std::vector<int> b) { int n, m; n = r.size(); m = b.size(); if (r[n-1] < b[0]){ long long ans = 0; for (int i=0; i<n; i++){ ans += r[n-1] - r[i]; } for (int i=0; i<m; i++){ ans += b[i] - b[0]; } ans += max(n, m) *(b[0] - r[n-1]); return ans; } long long DP[n][m]; DP[0][0] = b[0] - r[0]; for (int i=0; i<n; i++){ for (int j=0; j<m; j++){ if (i == 0 && j == 0) continue; if (i == 0){ DP[i][j] = DP[i][j-1] + abs(r[i] - b[j]); continue; } if (j == 0){ DP[i][j] = DP[i-1][j] + abs(r[i] - b[j]); continue; } DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + abs(r[i] - b[j]); } } return DP[n-1][m-1]; }
#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...