제출 #148533

#제출 시각아이디문제언어결과실행 시간메모리
148533Ian and 2-bit memory (#200)최적의 팀 구성 (FXCUP4_squad)C++17
100 / 100
2021 ms78908 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, CHTMultiset<T>* ptr) { Iterator z = this->emplace(k, m, 0, id); Iterator y = z++; Iterator x = y; while (Intersect(y, z)) { if (ptr) { ptr->Add(z->k, z->m, z->id, 0); } z = this->erase(z); } if (x != this->begin() && Intersect(--x, y)) { if (ptr) { ptr->Add(y->k, y->m, y->id, 0); } Intersect(x, y = this->erase(y)); } while ((y = x) != this->begin() && (--x)->p >= y->p) { if (ptr) { ptr->Add(y->k, y->m, y->id, 0); } 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, saa, sdd; 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, &saa); sd.Add(P[i], D[i], i, &sdd); } // for (auto it = sa.begin(); it != sa.end(); it++) printf("%d ", it->id); // puts(""); // for (auto it = sd.begin(); it != sd.end(); it++) printf("%d ", it->id); // puts(""); } long long ans; void check(int i, int j, long long x, long long y) { // printf(" %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y); if (i != j) { ans = max(ans, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y); } // i = 2, j = 3; // printf(" %d %d %lld\n", i, j, (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); vector<int> va = {ia->id}; if (!saa.empty()) va.push_back(saa.Query(x)->id); if (ia != sa.begin()) va.push_back(prev(ia)->id); if (next(ia) != sa.end()) va.push_back(next(ia)->id); vector<int> vb = {ib->id}; if (!sdd.empty()) vb.push_back(sdd.Query(x)->id); if (ib != sd.begin()) vb.push_back(prev(ib)->id); if (next(ib) != sd.end()) vb.push_back(next(ib)->id); for (int i : va)for (int j : vb) check(i, j ,X, Y); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...