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