This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int d(int x, int y) {return abs(x - y);}
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
int dp[100001][20];
dp[0][0] = d(r[0], b[0]);
const int block_size = 10;
for(int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + d(r[i], b[0]);
for(int i = 1; i < min(m, 10); i++) dp[0][i] = dp[0][i-1] + d(r[0], b[i]);
for(int i = 1; i < n; i++)
for(int j_index = -block_size; j_index < block_size; j_index++) {
if (j_index+i >= 0 && j_index+i < m) {
int j = j_index+i;
dp[i][j] = min({dp[i-1][j], (j == 0 ? 0 : dp[i][j-1]), (j == 0 ? 0 : dp[i-1][j-1])}) + d(r[i], b[j]);
}
}
return dp[n - 1][m - 1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |