제출 #1009964

#제출 시각아이디문제언어결과실행 시간메모리
1009964IS_Rushdi전선 연결 (IOI17_wiring)C++17
100 / 100
47 ms12740 KiB
// #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]+1 , i) - get(i-nums[i]*2+1 , i-nums[i]) + dp[i-nums[i]*2] ); } } 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 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...