| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1115278 | epicci23 | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "wiring.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll INF = 1e18;
ll min_total_length(vector<ll> R, vector<ll> B){
ll n = sz(R), m = sz(B);
ll ar[n+5],ar2[m+5];
for(ll i=0;i<n;i++) ar[i] = R[i];
for(ll i=0;i<m;i++) ar2[i] = B[i];
array<ll,2> range[n+5];
for(ll i=0;i<n;i++){
ll l = lower_bound(ar2,ar2+m,(i>0 ? ar[i-1] : -1)) - ar2;
ll r = lower_bound(ar2,ar2+m,(i+1<m ? ar[i+1] : INF)) - ar2;
l = max(0LL, l - 1);
r = min(m-1, r + 1);
range[i][0] = l;
range[i][1] = r;
}
vector<ll> dp(m+5, INF);
for(ll i=0;i<n;i++){
map<ll, ll> ndp;
for(ll j=range[i][0];j<=range[i][1];j++){
ll curi = INF;
if(i==0 || j==0) curi = 0;
if(j>0) curi = min(curi, dp[j-1]);
curi = min(curi, dp[j]);
if(ndp.count(j-1)) curi=min(curi, ndp[j-1]);
if(ndp.count(j)) ndp[j] = min(ndp[j], curi + abs(ar[i] - ar2[j]));
else ndp[j] = curi + abs(ar[i] - ar2[j]);
}
for(auto x:ndp) dp[x.first] = x.second;
}
return dp[m-1];
}
/*void _(){
ll n,m;
cin >> n >> m;
ll ar[n+5],ar2[m+5];
for(ll i=0;i<n;i++) cin >> ar[i];
for(ll i=0;i<m;i++) cin >> ar2[i];
array<ll,2> range[n+5];
for(ll i=0;i<n;i++){
ll l = lower_bound(ar2,ar2+m,(i>0 ? ar[i-1] : -1)) - ar2;
ll r = lower_bound(ar2,ar2+m,(i+1<m ? ar[i+1] : INF)) - ar2;
l--;
r++;
l = max(0LL, l);
r = min(m-1, r);
range[i][0] = l;
range[i][1] = r;
}
vector<ll> dp(m+5, INF);
for(ll i=0;i<n;i++){
map<ll, ll> ndp;
for(ll j=range[i][0];j<=range[i][1];j++){
ll curi = INF;
if(i==0 || j==0) curi = 0;
if(j>0) curi = min(curi, dp[j-1]);
curi = min(curi, dp[j]);
if(ndp.count(j-1)) curi=min(curi, ndp[j-1]);
if(ndp.count(j)) ndp[j] = min(ndp[j], curi + abs(ar[i] - ar2[j]));
else ndp[j] = curi + abs(ar[i] - ar2[j]);
}
for(auto x:ndp) dp[x.first] = x.second;
}
cout << dp[m-1] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
ll tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/