#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())
using ll = long long;
const ll infll = (ll)1e18 + 7;
ll min_total_length(vector <int> r, vector <int> b){
int n = isz(r), m = isz(b);
vector <vector <ll>> dp(n + 1, vector <ll>(m + 1, infll));
dp[0][0] = 0;
ForE(i, 0, n){
ForE(j, 0, m){
if (i < n and j > 0){
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + abs(r[i] - b[j - 1]));
}
if (i > 0 and j < m){
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + abs(r[i - 1] - b[j]));
}
if (i < n and j < m){
dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(r[i] - b[j]));
}
}
}
return dp[n][m];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
560 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
556 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
552 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
428 KB |
Output is correct |
3 |
Runtime error |
98 ms |
262144 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
97 ms |
262144 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Runtime error |
96 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
560 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
556 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
552 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
0 ms |
300 KB |
Output is correct |
18 |
Correct |
1 ms |
428 KB |
Output is correct |
19 |
Runtime error |
98 ms |
262144 KB |
Execution killed with signal 9 |
20 |
Halted |
0 ms |
0 KB |
- |