제출 #148436

#제출 시각아이디문제언어결과실행 시간메모리
148436Ian and 2-bit memory (#200)최적의 팀 구성 (FXCUP4_squad)C++17
19 / 100
905 ms76664 KiB
#include <bits/stdc++.h> using namespace std; #include "squad.h" // [Convex Hull Trick (CHT)] // https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h // https://wcipeg.com/wiki/Convex_hull_trick // Add lines of the form kx + m // Query maximum values at points x template<typename T> struct CHTLine { T k, m; mutable T p; int id; CHTLine(T k_, T m_, T p_, int id_) : k(k_), m(m_), p(p_), id(id_) {} bool operator<(const CHTLine<T>& o) const { return k < o.k; } bool operator<(const T& x) const { return p < x; } }; template<typename T> constexpr T CHTINF; template<> constexpr int CHTINF<int> = INT_MAX; template<> constexpr long long CHTINF<long long> = LLONG_MAX; template<> constexpr float CHTINF<float> = HUGE_VALF; template<> constexpr double CHTINF<double> = HUGE_VAL; template<> constexpr long double CHTINF<long double> = HUGE_VALL; template<typename T> struct CHTMultiset : multiset<CHTLine<T>, less<>> { // reimplemented below for integral T T Divide(T a, T b) { return a / b; } using Iterator = typename multiset<CHTLine<T>, less<>>::iterator; bool Intersect(Iterator x, Iterator y) { if (y == this->end()) { x->p = CHTINF<T>; return false; } if (x->k == y->k) x->p = x->m > y->m ? CHTINF<T> : -CHTINF<T>; else x->p = Divide(y->m - x->m, x->k - y->k); return x->p >= y->p; } void Add(T k, T m, int id) { Iterator z = this->emplace(k, m, 0, id); Iterator y = z++; Iterator x = y; while (Intersect(y, z)) z = this->erase(z); if (x != this->begin() && Intersect(--x, y)) Intersect(x, y = this->erase(y)); while ((y = x) != this->begin() && (--x)->p >= y->p) Intersect(x, this->erase(y)); } Iterator Query(T x) { // assert(!this->empty()); return this->lower_bound(x); // return l.k * x + l.m; } }; #define FLOOR_DIV(a, b) ((a) / (b) - (((a) ^ (b)) < 0 && (a) % (b))) template<> int CHTMultiset<int>::Divide(int a, int b) { return FLOOR_DIV(a, b); } template<> long long CHTMultiset<long long>::Divide(long long a, long long b) { return FLOOR_DIV(a, b); } #undef FLOOR_DIV CHTMultiset<long double> sa, sd; vector<int> aa, dd, pp; // a * x + p * y // (a + p * y / x) * x void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){ aa = A; dd = D; pp = P; int N = A.size(); for (int i = 0; i < N; i++) { sa.Add(P[i], A[i], i); sd.Add(P[i], D[i], i); } } long long ans; void check(CHTMultiset<long double>::Iterator ia, CHTMultiset<long double>::Iterator ib, long long x, long long y) { if (ia->id != ib->id) { int i = ia->id, j = ib->id; ans = max(ans, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y); } } long long BestSquad(int X, int Y){ ans = LLONG_MIN; long double x = (long double) Y / X; auto ia = sa.Query(x); auto ib = sd.Query(x); check(ia, ib, X, Y); if (ia != sa.begin()) { if (ib != sd.begin()) check(prev(ia), prev(ib), X, Y); check(prev(ia), ib, X, Y); if (next(ib) != sd.end()) check(prev(ia), next(ib), X, Y); } if (ib != sd.begin()) check(ia, prev(ib), X, Y); check(ia, ib, X, Y); if (next(ib) != sd.end()) check(ia, next(ib), X, Y); if (next(ia) != sa.end()) { if (ib != sd.begin()) check(next(ia), prev(ib), X, Y); check(next(ia), ib, X, Y); if (next(ib) != sd.end()) check(next(ia), next(ib), X, Y); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...