이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back
//#define int ll
const int MOD=1e9+7;
const ll INF=1e16;
const int N=200005;
ll dp[N],cnt[N];
ll min_total_length(vector<int> r,vector<int> b)
{
vector<pll> v;
v.pb({-INF,-1});
for(int i=0;i<r.size();i++) v.pb({r[i],0});
for(int i=0;i<b.size();i++) v.pb({b[i],1});
sort(v.begin(),v.end());
dp[0]=0;
ll last=0,d=1,sum=0;
for(int i=1;i<v.size();i++)
{
if(v[i-1].S!=v[i].S)
{
dp[i]=INF;
ll tmp=0,cur=i-1;
while(v[cur].S==v[i-1].S)
{
tmp+=v[i].F-v[cur].F;
//cout<<cur<<":"<<tmp<<"&"<<dp[cur]<<"&"<<dp[cur-1]<<" ";
dp[i]=min({dp[i],dp[cur]+tmp,dp[cur-1]+tmp});
cur--;
}
last=i-1,d=1,sum=v[i].F-v[i-1].F;
}
else
{
dp[i]=dp[i-1]+v[i].F-v[last].F;
if(v[last].S==v[last-d].S)
{
sum+=v[i].F-v[last-d].F;
dp[i]=min(dp[i],dp[last-d-1]+sum),d++;
}
}
//cout<<dp[i]<<"\n";
}
return dp[v.size()-1];
}
/*
int main()
{
ll n,m;
//cin>>n>>m;
n=200,m=200;
vector<int> a(n),b(m);
rep(i,n)
{
//cin>>a[i];
a[i]=1e9-i;
}
rep(i,m)
{
//cin>>b[i];
b[i]=1e9-(n-1)-i;
}
cout<<min_total_length(a,b);
}
*/
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0;i<r.size();i++) v.pb({r[i],0});
| ~^~~~~~~~~
wiring.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<b.size();i++) v.pb({b[i],1});
| ~^~~~~~~~~
wiring.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |