| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 660598 | Trisanu_Das | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "wiring.h"
long long dp[200001];
long long dp2[200001];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<pair<int,int>> ss;
int n = r.size();
int m = b.size();
for(long long i = 0;i<n;i++) ss.pb({r[i],0});
for(long long i = 0;i<m;i++) ss.pb({b[i],1});
vector<vector<long long>> tt;
sort(ss.begin(),ss.end());
int ind2 = 0;
while(ind2<ss.size()){
int cur = ss[ind2].b;
tt.pb({});
while(ind2<ss.size()){
if(ss[ind2].b == cur){
tt[tt.size() - 1].pb(ss[ind2].a);
ind2++;
}
else break;
}
}
for(long long i = 0;i <= n+m;i++) dp[i] = 1e18;
dp[0] = 0;;
for(long long i = 1;i<tt.size();i++){
for(long long j = 0;j <= tt[i].size();j++) dp2[j] = 1e18;
vector<long long> mi;
vector<long long> mi2;
for(long long j = 0;j <= tt[i - 1].size();j++){
mi.pb((long long)1e18);
mi2.pb((long long)1e18);
}
long long xx = tt[i - 1].size();
long long su = 0;
long long ind = xx - 1;
for(long long j = 0;j <= tt[i - 1].size();j++){
if(j>0){
su+ = tt[i - 1][ind];
ind--;
}
mi[j] = min(mi[j],dp[xx - j]+tt[i - 1].back()*j - su);
if(j>0) mi[j] = min(mi[j - 1],mi[j]);
}
ind = 0;
for(long long j = tt[i - 1].size();j >= 0;j--){
mi2[j] = min(mi2[j],dp[xx - j] - su+tt[i][0]*j);
if(j<tt[i - 1].size()) mi2[j] = min(mi2[j],mi2[j+1]);
if(j>0){
su -= tt[i - 1][ind];
ind++;
}
}
long long kk = 0;
for(long long j = 0;j <= tt[i].size();j++){
if(j > 0) kk += tt[i][j - 1];
dp2[j] = min(dp2[j],mi[min(j,(long long)xx)] - tt[i - 1].back()*j+kk);
if(j <= xx) dp2[j] = min(dp2[j],mi2[j] - tt[i][0]*j+kk);
for(long long j = 0;j <= tt[i].size();j++) dp[j] = dp2[j];
}
return dp[tt.back().size()];
}
}