This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/agc018/tasks/agc018_c" #include <iostream> #include <vector> #include "library/datastructure/util/priority_sum.hpp" #include "library/util/permutation.hpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int x, y, z; std::cin >> x >> y >> z; const int n = x + y + z; std::vector<long long> b(n), c(n), d(n); long long sum_a = 0; for (int i = 0; i < n; i++) { long long a, x, y; std::cin >> a >> x >> y; b[i] = a - x; c[i] = a - y; d[i] = x - y; sum_a += a; } auto p = suisen::Permutation::index_sort(b); b = p.permute(b); c = p.permute(c); d = p.permute(d); std::vector<long long> sum_t(n); suisen::MaximumPrioritySum<long long> topk_t; for (int i = n - 1; i >= y - 1; --i) { if (i <= y + z - 1) { sum_t[i] = topk_t.get_sum(); topk_t.incr_k(); } topk_t.insert(c[i]); } std::vector<long long> sum_h(n); suisen::MaximumPrioritySum<long long> topk_h; long long sum_b = 0; for (int i = 0; i <= y + z - 1; ++i) { sum_b += b[i]; topk_h.insert(d[i]); if (i >= y - 1) { sum_h[i] = topk_h.get_sum() + sum_b; topk_h.incr_k(); } } long long ans = 0; for (int i = y - 1; i < y + z; i++) { ans = std::max(ans, sum_a - (sum_h[i] + sum_t[i])); } std::cout << ans << std::endl; return 0; }
#line 1 "test/src/datastructure/util/priority_sum/agc018_c.test.cpp" #define PROBLEM "https://atcoder.jp/contests/agc018/tasks/agc018_c" #include <iostream> #include <vector> #line 1 "library/datastructure/util/priority_sum.hpp" #include <queue> #include <utility> namespace suisen { namespace internal::priority_sum { template <typename T, typename Comparator, typename RevComparator> struct PrioritySum { using value_type = T; using comparator_type = Comparator; using reverse_comparator_type = RevComparator; PrioritySum() : PrioritySum(0) {} PrioritySum(int k) : _k(k), _sum(0), _cmp(), _rev_cmp(), _head_k(_cmp), _del_head_k(_cmp), _tail(_rev_cmp), _del_tail(_rev_cmp) {} value_type get_sum() const { return _sum; } void insert(const value_type &v) { _sum += v; _head_k.push(v); fix(); } void erase(const value_type &v) { if (_head_k.size() and v == _head_k.top()) { _sum -= v; _head_k.pop(); } else if (_head_k.size() and _rev_cmp(v, _head_k.top())) { _sum -= v; _del_head_k.push(v); } else { _del_tail.push(v); } fix(); } int get_k() const { return _k; } void set_k(int new_k) { _k = new_k, fix(); } void incr_k() { set_k(get_k() + 1); } void decr_k() { set_k(get_k() - 1); } int size() const { return int((_head_k.size() + _tail.size()) - (_del_head_k.size() + _del_tail.size())); } private: int _k; value_type _sum; comparator_type _cmp; reverse_comparator_type _rev_cmp; std::priority_queue<value_type, std::vector<value_type>, comparator_type> _head_k, _del_head_k; std::priority_queue<value_type, std::vector<value_type>, reverse_comparator_type> _tail, _del_tail; void fix() { while (int(_head_k.size() - _del_head_k.size()) < _k and _tail.size()) { value_type v = std::move(_tail.top()); _tail.pop(); if (_del_tail.size() and _del_tail.top() == v) { _del_tail.pop(); } else { _sum += v; _head_k.push(std::move(v)); } } while (int(_head_k.size() - _del_head_k.size()) > _k) { value_type v = std::move(_head_k.top()); _head_k.pop(); if (_del_head_k.size() and _del_head_k.top() == v) { _del_head_k.pop(); } else { _sum -= v; _tail.push(std::move(v)); } } } }; } // internal::priority_sum template <typename T> using MaximumPrioritySum = internal::priority_sum::PrioritySum<T, std::less<T>, std::greater<T>>; template <typename T> using MinimumPrioritySum = internal::priority_sum::PrioritySum<T, std::greater<T>, std::less<T>>; } // namespace suisen #line 1 "library/util/permutation.hpp" #include <algorithm> #include <cassert> #include <numeric> #line 8 "library/util/permutation.hpp" namespace suisen { struct Permutation : public std::vector<int> { using base_type = std::vector<int>; using base_type::base_type; Permutation() : Permutation(0) {} Permutation(std::size_t n) : Permutation(int(n)) {} Permutation(int n) : base_type(n) { std::iota(begin(), end(), 0); } Permutation(const std::vector<int>& a) : std::vector<int>(a) {} Permutation(std::vector<int>&& a) : std::vector<int>(std::move(a)) {} // returns b s.t. b[i] = a[p[i]] template <typename T> std::vector<T> permute(const std::vector<T>& a) const { const int n = a.size(); std::vector<T> res(n); for (int i = 0; i < n; ++i) res[i] = a[(*this)[i]]; return res; } // returns b s.t. b[p[i]] = a[i] template <typename T> std::vector<T> inv_permute(const std::vector<T>& a) const { const int n = a.size(); std::vector<T> res(n); for (int i = 0; i < n; ++i) res[(*this)[i]] = a[i]; return res; } // returns p * q s.t. (p * q)[i] = p[q[i]] friend Permutation operator*(const Permutation& p, const Permutation& q) { return q.permute(p); } Permutation& operator*=(const Permutation& q) { return *this = *this * q; } Permutation inv() const { const int n = size(); Permutation res(n); for (int i = 0; i < n; ++i) res[(*this)[i]] = i; return res; } Permutation pow(long long k) const { assert(k >= 0); const int n = size(); std::vector<int8_t> seen(n, false); Permutation res(n); for (int s = 0; s < n; ++s) { if (seen[s]) continue; std::vector<int> cycle { s }; for (int v = (*this)[s]; v != s; v = (*this)[v]) cycle.push_back(v); const int l = cycle.size(); for (int j = 0; j < l; ++j) { int v = cycle[j]; seen[v] = true; res[v] = cycle[(j + k) % l]; } } return res; } template <typename T, typename Comp = std::less<T>> static Permutation index_sort(const std::vector<T>& a, Comp comp = Comp{}) { Permutation p(a.size()); std::sort(p.begin(), p.end(), [&](int i, int j) { return comp(a[i], a[j]); }); return p; } }; template <typename hash_t> struct PermutationHash { hash_t operator()(const Permutation &p) const { return hash(p); } /** * minimal perfect hash function for permutations. * complexity: O(n) time, O(n) extra space * reference: https://twitter.com/noshi91/status/1452081886025555972?s=20 */ static hash_t hash(const Permutation &per) { hash_t h = 0; const int n = per.size(); Permutation p = per; Permutation q = per.inv(); for (int i = n - 1; i >= 0; --i) { h = h * (i + 1) + p[i]; p[q[i]] = p[i]; q[p[i]] = q[i]; } return h; } static Permutation unhash(int n, hash_t h) { Permutation p = Permutation(n), q = p; for (int i = 0; i < n; ++i) { p[i] = h % (i + 1), q[i] = q[p[i]]; q[p[i]] = p[q[i]] = i; h /= i + 1; } return p; } }; } // namespace suisen #line 8 "test/src/datastructure/util/priority_sum/agc018_c.test.cpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int x, y, z; std::cin >> x >> y >> z; const int n = x + y + z; std::vector<long long> b(n), c(n), d(n); long long sum_a = 0; for (int i = 0; i < n; i++) { long long a, x, y; std::cin >> a >> x >> y; b[i] = a - x; c[i] = a - y; d[i] = x - y; sum_a += a; } auto p = suisen::Permutation::index_sort(b); b = p.permute(b); c = p.permute(c); d = p.permute(d); std::vector<long long> sum_t(n); suisen::MaximumPrioritySum<long long> topk_t; for (int i = n - 1; i >= y - 1; --i) { if (i <= y + z - 1) { sum_t[i] = topk_t.get_sum(); topk_t.incr_k(); } topk_t.insert(c[i]); } std::vector<long long> sum_h(n); suisen::MaximumPrioritySum<long long> topk_h; long long sum_b = 0; for (int i = 0; i <= y + z - 1; ++i) { sum_b += b[i]; topk_h.insert(d[i]); if (i >= y - 1) { sum_h[i] = topk_h.get_sum() + sum_b; topk_h.incr_k(); } } long long ans = 0; for (int i = y - 1; i < y + z; i++) { ans = std::max(ans, sum_a - (sum_h[i] + sum_t[i])); } std::cout << ans << std::endl; return 0; }