Submission #552729

#TimeUsernameProblemLanguageResultExecution timeMemory
552729timreizinWiring (IOI17_wiring)C++17
100 / 100
112 ms13460 KiB
#include "wiring.h" #include <vector> #include <algorithm> #include <set> using namespace std; using ll = long long; ll min_total_length(vector<int> r, vector<int> b) { vector<pair<ll, bool>> points; for (int i : r) points.emplace_back(i, 0); for (int i : b) points.emplace_back(i, 1); sort(points.begin(), points.end()); int n = points.size(); vector<ll> dp(n, 1e18); multiset<ll> updBig, updSmall; vector<ll> cur, prev; cur.push_back(0); ll sum = 0, cntCur = 1; for (int i = 1; i < n; ++i) { if (points[i].second != points[i - 1].second) { cntCur = 0; sum = 0; updBig.clear(); updSmall.clear(); ll tmp = 0; reverse(cur.begin(), cur.end()); prev.clear(); for (int j = 0; j < cur.size(); ++j) { tmp += points[i - 1].first - points[i - 1 - j].first; cur[j] += tmp; updBig.insert(cur[j] + (j + 1) * (points[i].first - points[i - 1].first)); } prev = cur; cur.clear(); } ++cntCur; sum += points[i].first - points[i - cntCur + 1].first; cur.push_back(dp[i - 1]); if (updBig.empty() && updSmall.empty()) continue; dp[i] = dp[i - cntCur] + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first) + sum; if (!updBig.empty()) dp[i] = min(dp[i], *updBig.begin() + sum); if (!updSmall.empty()) dp[i] = min(dp[i], *updSmall.begin() + sum + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first)); if (!updBig.empty()) { updBig.erase(updBig.find(prev[cntCur - 1] + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first))); updSmall.insert(prev[cntCur - 1]); } } return dp.back(); }

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int j = 0; j < cur.size(); ++j)
      |                             ~~^~~~~~~~~~~~
#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...