제출 #968492

#제출 시각아이디문제언어결과실행 시간메모리
968492nguyentunglam전선 연결 (IOI17_wiring)C++17
7 / 100
29 ms19928 KiB
#include "wiring.h" #include<bits/stdc++.h> using namespace std; const int N = 1010; long long dp[N][N]; int a[N], b[N]; int c[N], d[N]; int g[2][N]; long long min_total_length(std::vector<int> R, std::vector<int> B) { int n = R.size(), m = B.size(); for(int i = 1; i <= n; i++) a[i] = R[i - 1]; for(int i = 1; i <= m; i++) b[i] = B[i - 1]; a[n + 1] = b[m + 1] = 1e9; for(int i = 1, j = 1, k = 0, sum = 0; i <= n || j <= m;) { // cout << sum << endl; if (a[i] < b[j]) { sum += d[k] == 1; // cout << i << " " << sum << endl; g[0][i] = sum; c[++k] = a[i++]; d[k] = 0; } else { sum += d[k] == 0; g[1][j] = sum; c[++k] = b[j++]; d[k] = 1; } } // for(int i = 1; i <= n; i++) cout << g[0][i] << " "; cout << endl; // for(int i = 1; i <= m; i++) cout << g[1][i] << " "; cout << endl; memset(dp, 61, sizeof(dp)); dp[0][0] = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if (abs(g[0][i] - g[1][j]) == 1) { dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + abs(a[i] - b[j]); } return dp[n][m]; } #ifdef ngu int main() { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); int n, m; assert(2 == scanf("%d %d", &n, &m)); vector<int> r(n), b(m); for(int i = 0; i < n; i++) assert(1 == scanf("%d", &r[i])); for(int i = 0; i < m; i++) assert(1 == scanf("%d", &b[i])); long long res = min_total_length(r, b); printf("%lld\n", res); return 0; } #endif // ngu
#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...