| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1045958 | LittleOrange | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
ll n = r.size(),m = b.size();
if (n<=200&&m<=200){
vector<pair<ll,ll>> v;
for(ll i : r) v.push_back({i,0});
for(ll i : b) v.push_back({i,1});
sort(v.begin(),v.end());
ll w = n+m;
vector<vector<ll>> dp(w,vector<ll>(w,big));
for(ll i = 0;i<w-1;i++){
if (v[i].second!=v[i+1].second){
dp[i][i+1] = v[i+1].first-v[i].first;
}
}
for(ll i = w-1;i>=0;i--){
for(ll j = i+2;j<w;j++){
if (v[i].second!=v[j].second){
dp[i][j] = min(dp[i][j],(v[j].first-v[i].first)+dp[i+1][j-1]);
}
if (v[i].second){
auto it = lower_bound(r.begin(),r.end(),v[i].first);
if (it!=r.end()){
dp[i][j] = min(dp[i][j],(*it-v[i].first)+dp[i+1][j]);
}
}else{
auto it = lower_bound(b.begin(),b.end(),v[i].first);
if (it!=b.end()){
dp[i][j] = min(dp[i][j],(*it-v[i].first)+dp[i+1][j]);
}
}
if (v[j].second){
auto it = lower_bound(r.begin(),r.end(),v[j].first);
if (it!=r.begin()){
dp[i][j] = min(dp[i][j],(v[j].first-*--it)+dp[i][j-1]);
}
}else{
auto it = lower_bound(b.begin(),b.end(),v[j].first);
if (it!=b.begin()){
dp[i][j] = min(dp[i][j],(v[j].first-*--it)+dp[i][j-1]);
}
}
for(ll k = i+1;k+2<=j;k++){
dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);
}
}
}
return dp[0][w-1];
}
ll c = min(n,m);
ll ret = 0;
for(ll i = 0;i<c;i++){
ret += b[i]-r[i+n-c];
}
if (n>m){
for(ll i = 0;i<n-m;i++){
ret += b[0] - r[i];
}
}
if(m>n){
for(ll i = n;i<m;i++){
ret += b[i] - r.back();
}
}
return ret;
}