Submission #1218610

#TimeUsernameProblemLanguageResultExecution timeMemory
1218610newsboyPalembang Bridges (APIO15_bridge)C++20
100 / 100
64 ms6076 KiB
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <iomanip> #include <set> #include <map> #include <numeric> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <bitset> #include <queue> #include <deque> #include <stack> #include <cmath> #include <tuple> #include <cassert> #include <array> #include <list> #include <random> #include <initializer_list> using namespace std; using ll = long long; using u64 = unsigned long long; using db = double; using ld = long double; constexpr ll INF = 1E18; constexpr ll MIN = -INF; constexpr ll MAX = INF; constexpr ll N = 1E5; void solve() { ll K, N; cin >> K >> N; vector<array<ll, 2>> vec; ll add = 0; for (ll i = 0; i < N; ++i) { char P, Q; ll s, t; cin >> P >> s >> Q >> t; if (P == Q) { add += abs(s - t); } else { add += 1; vec.push_back({ s, t }); } } sort(vec.begin(), vec.end(), [&](auto a, auto b) { return a[0] + a[1] < b[0] + b[1]; }); priority_queue<ll> lpq; priority_queue<ll, vector<ll>, greater<ll>> rpq; ll totl = 0, totr = 0; auto push = [&](ll x) -> void { ll med = (lpq.empty() ? MAX : lpq.top()); if (x <= med) { lpq.push(x); totl += x; } else { rpq.push(x); totr += x; } while (lpq.size() - 1 > rpq.size()) { ll h = lpq.top(); rpq.push(h); lpq.pop(); totr += h; totl -= h; } while (lpq.size() < rpq.size()) { ll h = rpq.top(); lpq.push(h); rpq.pop(); totl += h; totr -= h; } }; vector<ll> pref(vec.size() + 1); for (ll i = 0; i < vec.size(); ++i) { push(vec[i][0]); push(vec[i][1]); pref[i + 1] = totr - totl; } ll ans = pref[vec.size()]; if (K == 2) { while (!lpq.empty()) lpq.pop(); while (!rpq.empty()) rpq.pop(); totl = totr = 0; for (ll i = ll(vec.size()) - 1; i >= 0; --i) { push(vec[i][0]); push(vec[i][1]); ans = min(ans, pref[i] + totr - totl); } } cout << ans + add << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; /*cin >> t;*/ while (t--) { solve(); } return 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...