| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1365624 | Charizard2021 | Wiring (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
long long min_total_length(vector<int32_t> r, vector<int32_t> b) {
vector<vector<int> > a;
a.push_back({0});
vector<int> cur;
int j1 = 0;
int j2 = 0;
while(j1 < r.size() || j2 < b.size()){
if(j1 >= r.size() || (j2 < b.size() && b[j2] < r[j1])){
swap(j1, j2);
swap(r, b);
if(!cur.empty()){
a.push_back(cur);
}
cur.clear();
}
cur.push_back(r[j1]);
j1++;
}
a.push_back(cur);
a.push_back({2000000000});
vector<int> dp1(1, 0);
vector<int> dp2(1, 0);
for(int i = 1; i < a.size() - 1; i++){
int s = a[i].size();
vector<int> dp(s + 1, M);
int e = M;
int f = 0;
for(int j = 1; j <= s; j++){
if(dp1.size() > j){
e = min(e , dp1[j]);
}
f += a[i][j - 1] - a[i - 1].back();
dp[j] = min(e + f, M);
}
e = M;
f = 0;
for(int j = dp2.size() - 1; j > s; j--){
e = min(e , dp2[j]);
}
for(int j = 1; j <= s; j++){
f += a[i][s - j] - a[i][0];
}
for(int j = s; j >= 1; j--){
if(dp2.size() > j){
e = min(e, dp2[j]);
}
dp[j] = min(e + f, dp[j]);
f -= a[i][j - 1] - a[i][0];
}
dp[0] = min(dp1[0] , dp2[0]);
dp1.assign(s + 1, 0);
dp2.assign(s + 1, 0);
int w1 = 0;
int w2 = 0;
for(int j = 0; j <= s; j++){
dp1[j] = min(dp[s - j] + w1, M);
dp2[j] = min(dp[s - j] + w2, M);
if(j != s){
w1 += a[i][s - 1] - a[i][s - j - 1];
}
if(j != s){
w2 += a[i + 1][0] - a[i][s - j - 1];
}
}
}
return dp1[0];
}