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 "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int>r, vector<int>b) {
const int n = (int)r.size(), m = (int)b.size();
long long dp[45][45];
for(int i = 0 ; i <= 39 ; i++)
for(int j = 0 ; j <= 39 ; j++)
dp[i][j] = 1e15;
dp[0][0] = 0;
int a = 0, c = 0;
vector<pair<int,int>>v;
bool ok = 1;
int f, cnt = 0;
for(int i = 0 ; i < n+m ; i++) {
if(a == n) {v.push_back({1, b[c++]}); continue;}
if(c == m) {v.push_back({0, r[a++]}); continue;}
if(r[a] < b[c])
v.push_back({0, r[a++]});
else
v.push_back({1, b[c++]});
if(i == 0)
f = v.back().first;
if(ok && v.back().first == f)
cnt++;
else ok = 0;
}
int del = 0;
int A = 0, B = 0;
if(f) B = cnt;
else A = cnt;
while(A+B < n+m) {
int len = 0;
c = v[A+B].first;
int ii = A+B;
while(ii < n+m && v[ii].first == c)
ii++, len++;
ii = A+B-1;
c = 1 - c;
int prev = 0;
while(ii >= 0 && v[ii].first == c)
ii--, prev++;
c = 1 - c;
int mn = INT_MAX;
for(int ii = A+B ; ii < A+B+len ; ii++) {
if(c == 0) {
int i = A+(ii - (A+B)+1);
for(int j = B-prev+1 ; j <= B ; j++) {
for(int k = B-prev+1 ; k <= B ; k++)
dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-del] + abs(v[ii].second - v[k+A-1].second));
for(int k = A+(ii - (A+B)+1) ; k <= A+len ; k++)
dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-del][j-1-del] + abs(v[j+A-1].second - v[k+B-1].second));
dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-1-del] + abs(v[ii].second - v[j+A-1].second));
mn = min(i-1-del, j-1-del);
}
} else {
int j = B + (ii - (A+B)+1);
for(int i = A-prev+1 ; i <= A ; i++) {
for(int k = A-prev+1 ; k <= A ; k++)
dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-del][j-1-del] + abs(v[ii].second - v[k+B-1].second));
for(int k = B+(ii - (A+B)+1) ; k <= B+len ; k++)
dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-del] + abs(v[i+B-1].second - v[k+A-1].second));
dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-1-del] + abs(v[ii].second - v[i+B-1].second));
mn = min(j-1-del, i-1-del);
}
}
}
if(c)
B += len;
else
A += len;
int d = mn;
del += d;
for(int i = 0 ; i <= 39 ; i++)
for(int j = 0 ; j <= 39 ; j++)
dp[i][j] = (i+d <= 39 && j+d <= 39 ? dp[i+d][j+d] : 1e15);
}
return dp[n-del][m-del];
}
Compilation message (stderr)
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:34:5: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
34 | if(f) B = cnt;
| ^~
# | 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... |