이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e10;
ll min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size();
int m = b.size();
ll ans = 0;
vector<pair<ll,int>>pre(1); pre[0] = {0,-1};
for(int i = 0; i < n; i++) pre.push_back({r[i],0});
for(int i = 0; i < m; i++) pre.push_back({b[i],1});
n +=m;
sort(pre.begin(),pre.end());
ll q[2] = {-inf,-inf};
ll d[n+1]; fill(d,d+n+1,inf);
for(int i = 1; i <= n; i++){
q[pre[i].second] = pre[i].first;
d[i] = min(d[i] , pre[i].first - q[pre[i].second^1]);
}
q[0] = q[1] = inf;
for(int i = n; i >= 1; i--){
q[pre[i].second] = pre[i].first;
d[i] = min(d[i] , q[pre[i].second^1]-pre[i].first);
}
for(int i = 1; i <= n; i++) pre[i].first += pre[i-1].first;
ll dp[n+1]; fill(dp,dp+n+1,1e18); dp[0] = 0;
ll nums[n+1]; fill(nums,nums+n+1,0);
function<ll(int l,int r)>get=[&](int l,int r){
return pre[r].first - pre[l-1].first;
};
for(int i = 1; i <= n; i++){
dp[i] = dp[i-1] + d[i];
if(pre[i].second == pre[i-1].second) nums[i] = nums[i-1]+1;
else nums[i] = 1;
if(nums[i] <= nums[i-nums[i]]){
dp[i] = min(dp[i],
get(i-nums[i] , i) - get(i-nums[i]*2 , i-nums[i]) + dp[i-nums[i]*2-1]
);
}
}
return dp[n];
}
// int main(){
// cout << min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10}) << '\n';
// }
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:10:8: warning: unused variable 'ans' [-Wunused-variable]
10 | ll ans = 0;
| ^~~
# | 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... |