제출 #1009332

#제출 시각아이디문제언어결과실행 시간메모리
1009332IS_Rushdi전선 연결 (IOI17_wiring)C++17
0 / 100
1 ms436 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size(); int m = b.size(); long long ans = 0; vector<pair<int,int>>m1(n),m2(m); for(int i = 0; i < n; i++){ int nxt = lower_bound(b.begin(), b.end(), r[i]) - b.begin(); int mn = 2e9; int idx = nxt; if(nxt != m) mn = b[nxt] - r[i]; nxt--; if(nxt >= 0 && r[i] - b[nxt] < mn){ mn = r[i] - b[nxt]; idx = nxt-1; } m1[i] = {mn,idx}; } for(int i = 0; i < m; i++){ int nxt = lower_bound(r.begin(),r.end(), b[i]) - r.begin(); int mn = 2e9; int idx = nxt; if(nxt != m) mn = r[nxt] - b[i]; nxt--; if(nxt >= 0 && b[i] - r[nxt] < mn){ mn = b[i] - r[nxt]; idx = nxt-1; } m2[i] = {mn,idx}; } int i = 0,j=0; while(i < n && j < m){ if(abs(r[i]-b[j]) < m1[i].first + m2[j].first){ ans += abs(r[i]-b[j]); i++,j++; }else{ ans += m1[i].first; i++; } } while(i < n) ans += m1[i++].first; while(j < m) ans += m2[j++].first; return ans; } // int main(){ // cout << min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10}) << '\n'; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...