Submission #269480

#TimeUsernameProblemLanguageResultExecution timeMemory
269480hamerinWiring (IOI17_wiring)C++17
0 / 100
90 ms14060 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; #define iterall(cont) cont.begin(), cont.end() #define prec(n) setprecision(n) << fixed i64 inf = numeric_limits<i64>::max() / 3; i64 min_total_length(vector<int> r, vector<int> b) { const int R = r.size(); const int B = b.size(); vector<i64> Rv, Bv; Rv.emplace_back(-inf); Bv.emplace_back(-inf); copy(iterall(r), back_inserter(Rv)); copy(iterall(b), back_inserter(Bv)); Rv.emplace_back(inf); Bv.emplace_back(inf); vector<pair<int, bool>> seq; transform(iterall(r), back_inserter(seq), [](int x) -> decltype(seq)::value_type { return {x, true}; }); transform(iterall(b), back_inserter(seq), [](int x) -> decltype(seq)::value_type { return {x, false}; }); sort(iterall(seq)); int n = 1; vector<int> rhm(1), bhm(1); vector<i64> rs(1), bs(1); for (auto [el, clr] : seq) { if (clr) rhm.emplace_back(1); else rhm.emplace_back(0); if (!clr) bhm.emplace_back(1); else bhm.emplace_back(0); if (clr) rs.emplace_back(el); else rs.emplace_back(0); if (!clr) bs.emplace_back(el); else bs.emplace_back(0); rhm[n] += rhm[n - 1]; bhm[n] += bhm[n - 1]; rs[n] += rs[n - 1]; bs[n] += bs[n - 1]; ++n; } map<int, int> hmInterval; vector<i64> dp(R + B); hmInterval[0] = -1; for (int i = 0; i < R + B; i++) { auto [el, clr] = seq[i]; i64 d; if (clr) { auto it = lower_bound(iterall(Bv), el); d = min((*it) - el, el - (*prev(it))); } else { auto it = lower_bound(iterall(Rv), el); d = min((*it) - el, el - (*prev(it))); } dp[i] = (i ? dp[i - 1] : 0) + d; auto it = hmInterval.find(rhm[i + 1] - bhm[i + 1]); if (it != hmInterval.end()) { auto j = it->second; dp[i] = min(dp[i], dp[j] + abs(rs[i + 1] - rs[j + 1] - bs[i + 1] + bs[j + 1])); } hmInterval[rhm[i + 1] - bhm[i + 1]] = i; } return dp.back(); }
#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...