| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 757149 | alexander707070 | 장난감 기차 (IOI17_train) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e15;
int n,m;
long long red[MAXN],blue[MAXN];
long long raz[MAXN],zar[MAXN],ans;
unordered_map<long long,bool> li;
unordered_map<long long,long long> dp;
vector< pair<long long,int> > v;
long long st(long long x,long long y){
return x*1000000+y;
}
long long ff(int l,int r){
if(red[r]-blue[l]>raz[l] and n+m>500)return inf;
if(blue[l]-red[r]>zar[r] and n+m>500)return inf;
if(l==n and r==m)return abs(red[l]-blue[r]);
if(li[st(l,r)])return dp[st(l,r)];
li[st(l,r)]=true;
dp[st(l,r)]=inf;
if(l<n)dp[st(l,r)]=min(dp[st(l,r)],ff(l+1,r));
if(r<m)dp[st(l,r)]=min(dp[st(l,r)],ff(l,r+1));
if(l<n and r<m)dp[st(l,r)]=min(dp[st(l,r)],ff(l+1,r+1));
dp[st(l,r)]+=abs(red[l]-blue[r]);
return dp[st(l,r)];
}
long long min_total_length(vector<int> R,vector<int> B){
n=int(R.size()); m=int(B.size());
for(int i=1;i<=n;i++){
red[i]=R[i-1];
v.push_back({red[i],i});
}
for(int i=1;i<=m;i++){
blue[i]=B[i-1];
v.push_back({blue[i],n+i});
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
if(v[i].second<=n){
raz[v[i].second]=2*v[min(i+10,int(v.size())-1)].first-v[i].first;
}else{
zar[v[i].second-n]=2*v[min(i+10,int(v.size())-1)].first-v[i].first;
}
}
if(n<=m){
for(int i=1;i<=n;i++){
ans+=abs(blue[i]-red[i]);
}
for(int i=n+1;i<=m;i++){
ans+=abs(blue[i]-red[n]);
}
}else{
for(int i=m;i>=1;i--){
ans+=abs(blue[i]-red[n-(m-i)]);
}
for(int i=n-m;i>=1;i--){
ans+=abs(blue[1]-red[i]);
}
}
return min(ans,ff(1,1));
}
/*
int main(){
cout<<min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10})<<"\n";
}
*/