이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <set>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b)
{
if (r.back()<b.front())
{
long long x=min(r.size(),b.size());
long long ans=0;
for (long long i=0;i<x;i++)
ans+=abs(b[i]-r[i]);
for (long long i=x;i<r.size();i++)
ans+=min(abs(b.back()-r[i]),abs(b[0]-r[i]));
for (long long i=x;i<b.size();i++)
ans+=min(abs(b[i]-r.front()),abs(b[i]-r.back()));
return ans;
}
long long n=r.size(),m=b.size();
if (n<=1000&&m<=1000)
{
map<pair<long long,long long>,long long>dp;
set<vector<long long>>S;
S.insert({0,0,0});
dp[{0,0}]=0;
while (S.size())
{
long long i=(*begin(S))[1],j=(*begin(S))[2],co=(*begin(S))[0];
S.erase(*begin(S));
if (dp[{i,j}]!=co)
continue;
if (i==n&&j==m)
break;
if (i==n||j==m)
continue;
if (dp[{i+1,j+1}]==0)
{
dp[{i+1,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
S.insert({dp[{i+1,j+1}],i+1,j+1});
}
if (dp[{i+1,j}]==0)
{
dp[{i+1,j}]=dp[{i,j}]+abs(r[i]-b[j]);
S.insert({dp[{i+1,j}],i+1,j});
}
if (dp[{i,j+1}]==0)
{
dp[{i,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
S.insert({dp[{i,j+1}],i,j+1});
}
long long cost=dp[{i,j}]+abs(r[i]-b[j]);
if (dp[{i+1,j+1}]>cost)
{
dp[{i+1,j+1}]=cost;
S.insert({dp[{i+1,j+1}],i+1,j+1});
}
if (dp[{i+1,j}]>cost)
{
dp[{i+1,j}]=cost;
S.insert({dp[{i+1,j}],i+1,j});
}
if (dp[{i,j+1}]>cost)
{
dp[{i,j+1}]=cost;
S.insert({dp[{i,j+1}],i,j+1});
}
}
return dp[{n,m}];
}
long long dp[n+m+10]={};
vector<pair<long long,long long>>d;
for (long long i=0;i<n;i++)
d.push_back({r[i],0});
for (long long i=0;i<m;i++)
d.push_back({b[i],1});
sort(begin(d),end(d));
dp[0]=0;
for (long long i=1;i<=n+m;i++)
dp[i]=1e15+10;
for (long long i=1;i<=n+m;i++)
{
long long co=0;
for (long long j=max(1,i-7);j<i;j++)
{
if (d[i].second!=d[j].second)
co+=d[i].first-d[j].first;
dp[i]=min(dp[i],dp[j-1]+co);
}
}
return dp[n+m];
}
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:15:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (long long i=x;i<r.size();i++)
| ~^~~~~~~~~
wiring.cpp:17:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (long long i=x;i<b.size();i++)
| ~^~~~~~~~~
wiring.cpp:85:29: error: no matching function for call to 'max(int, long long int)'
85 | for (long long j=max(1,i-7);j<i;j++)
| ^
In file included from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
wiring.cpp:85:29: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
85 | for (long long j=max(1,i-7);j<i;j++)
| ^
In file included from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
wiring.cpp:85:29: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
85 | for (long long j=max(1,i-7);j<i;j++)
| ^
In file included from /usr/include/c++/10/algorithm:62,
from wiring.cpp:5:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
wiring.cpp:85:29: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
85 | for (long long j=max(1,i-7);j<i;j++)
| ^
In file included from /usr/include/c++/10/algorithm:62,
from wiring.cpp:5:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
wiring.cpp:85:29: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
85 | for (long long j=max(1,i-7);j<i;j++)
| ^