test/aoj/2725.LiCT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 11:34:20+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2725

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• Li-Chao-Tree (src/Optimization/LiChaoTree.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2725
// competitive-verifier: TLE 2
// competitive-verifier: MLE 512
#include <iostream>
#include <numeric>
#include "src/Optimization/LiChaoTree.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, T;
 cin >> N >> T;
 int t[N], p[N], f[N];
 for (int i= 0; i < N; ++i) cin >> t[i] >> p[i] >> f[i];
 int ord[N];
 iota(ord, ord + N, 0), sort(ord, ord + N, [&](int i, int j) { return f[i] < f[j]; });
 LiChaoTree lct([](int x, int a, long long b) {
  long long t= x - a;
  return b - t * t;
 });
 vector lcts(T + 1, lct.make_tree<MAXIMIZE>());
 long long ans= -1e9;
 for (int i= 0; i < N; ++i) {
  int I= ord[i], ti= t[I];
  for (int x= T; x >= ti; --x) {
   auto [val, _]= lcts[x - ti].query(f[I]);
   val= max(0ll, val) + p[I];
   ans= max(ans, val);
   lcts[x].insert(f[I], val);
  }
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/2725.LiCT.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2725
// competitive-verifier: TLE 2
// competitive-verifier: MLE 512
#include <iostream>
#include <numeric>
#line 2 "src/Optimization/LiChaoTree.hpp"
#include <limits>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/LiChaoTree.hpp"
template <class F, class T> class LiChaoTree {};
template <class F, class T, class... Prms> class LiChaoTree<F, std::tuple<T, Prms...>> {
 using R= result_type_t<F>;
 F f;
 const T LB, UB;
 std::vector<std::tuple<Prms...>> ps;
 template <MinMaxEnum sgn, bool persistent> class LiChaoTreeInterface {
  LiChaoTree *ins;
  struct Node {
   int id= -1;
   Node *ch[2]= {nullptr, nullptr};
  } *root;
  inline R eval(int id, T x) const { return std::apply(ins->f, std::tuple_cat(std::make_tuple(x), ins->ps[id])); }
  static inline bool cmp(const R &p, const R &n, int pi, int ni) {
   if constexpr (sgn == MINIMIZE) return p > n || (p == n && pi > ni);
   else return p < n || (p == n && pi > ni);
  }
  inline bool cmp(T x, int pi, int ni) const {
   if (ni == -1) return false;
   if (pi == -1) return true;
   return cmp(eval(pi, x), eval(ni, x), pi, ni);
  }
  static inline T ub(T r) {
   if constexpr (std::is_floating_point_v<T>) return r;
   else return r - 1;
  }
  inline void addl(Node *&t, int id, T xl, T xr) {
   if (!t) return t= new Node{id}, void();
   bool bl= cmp(xl, t->id, id), br= cmp(ub(xr), t->id, id);
   if (!bl && !br) return;
   if constexpr (persistent) t= new Node(*t);
   if (bl && br) return t->id= id, void();
   T xm= (xl + xr) / 2;
   if (cmp(xm, t->id, id)) std::swap(t->id, id), bl= !bl;
   if constexpr (std::is_floating_point_v<T>)
    if (xr - xl < 1e-9) return;
   bl ? addl(t->ch[0], id, xl, xm) : addl(t->ch[1], id, xm, xr);
  }
  inline void adds(Node *&t, int id, T l, T r, T xl, T xr) {
   if (r <= xl || xr <= l) return;
   if (l <= xl && xr <= r) return addl(t, id, xl, xr);
   if (!t) t= new Node;
   else if constexpr (persistent) t= new Node(*t);
   T xm= (xl + xr) / 2;
   adds(t->ch[0], id, l, r, xl, xm), adds(t->ch[1], id, l, r, xm, xr);
  }
  inline std::pair<R, int> query(const Node *t, T x, T xl, T xr) const {
   if (!t) return {R(), -1};
   T xm= (xl + xr) / 2;
   auto b= x < xm ? query(t->ch[0], x, xl, xm) : query(t->ch[1], x, xm, xr);
   if (t->id == -1) return b;
   R a= eval(t->id, x);
   return b.second != -1 && cmp(a, b.first, t->id, b.second) ? b : std::make_pair(a, t->id);
  }
 public:
  LiChaoTreeInterface()= default;
  LiChaoTreeInterface(LiChaoTree *ins): ins(ins), root(nullptr) {}
  void insert(const Prms &...args) { ins->ps.emplace_back(args...), addl(root, ins->ps.size() - 1, ins->LB, ins->UB); }
  // [l, r)
  void insert(const Prms &...args, T l, T r) {
   l= std::max(l, ins->LB), r= std::min(r, ins->UB);
   if (l < r) ins->ps.emplace_back(args...), adds(root, ins->ps.size() - 1, l, r, ins->LB, ins->UB);
  }
  // [l, UB)
  void insert(const Prms &...args, T l) { insert(args..., l, ins->UB); }
  std::pair<R, int> query(T x) const { return assert(ins->LB <= x && x < ins->UB), query(root, x, ins->LB, ins->UB); }
  const std::tuple<Prms...> &params(int id) const { return ins->ps[id]; }
 };
public:
 LiChaoTree(const F &f, T LB= -2e9, T UB= 2e9): f(f), LB(LB), UB(UB) {}
 template <MinMaxEnum sgn= MINIMIZE, bool persistent= false> LiChaoTreeInterface<sgn, persistent> make_tree() { return this; }
};
template <class F, class T, class U> LiChaoTree(F, T, U) -> LiChaoTree<F, argument_type_t<F>>;
template <class F, class T> LiChaoTree(F, T) -> LiChaoTree<F, argument_type_t<F>>;
template <class F> LiChaoTree(F) -> LiChaoTree<F, argument_type_t<F>>;
#line 7 "test/aoj/2725.LiCT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, T;
 cin >> N >> T;
 int t[N], p[N], f[N];
 for (int i= 0; i < N; ++i) cin >> t[i] >> p[i] >> f[i];
 int ord[N];
 iota(ord, ord + N, 0), sort(ord, ord + N, [&](int i, int j) { return f[i] < f[j]; });
 LiChaoTree lct([](int x, int a, long long b) {
  long long t= x - a;
  return b - t * t;
 });
 vector lcts(T + 1, lct.make_tree<MAXIMIZE>());
 long long ans= -1e9;
 for (int i= 0; i < N; ++i) {
  int I= ord[i], ti= t[I];
  for (int x= T; x >= ti; --x) {
   auto [val, _]= lcts[x - ti].query(f[I]);
   val= max(0ll, val) + p[I];
   ans= max(ans, val);
   lcts[x].insert(f[I], val);
  }
 }
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00	AC	13 ms	4 MB
g++-13	00_sample_01	AC	10 ms	4 MB
g++-13	00_sample_02	AC	9 ms	4 MB
g++-13	00_sample_03	AC	9 ms	4 MB
g++-13	00_sample_04	AC	9 ms	4 MB
g++-13	01_rando_medium_031	AC	9 ms	4 MB
g++-13	01_rando_medium_035	AC	9 ms	4 MB
g++-13	01_rando_medium_160	AC	9 ms	4 MB
g++-13	01_rando_medium_278	AC	9 ms	4 MB
g++-13	01_rando_medium_337	AC	8 ms	4 MB
g++-13	01_rando_medium_342	AC	9 ms	4 MB
g++-13	01_rando_medium_355	AC	9 ms	4 MB
g++-13	01_rando_medium_452	AC	9 ms	4 MB
g++-13	01_rando_medium_467	AC	9 ms	4 MB
g++-13	01_rando_medium_665	AC	9 ms	4 MB
g++-13	02_rando_large_000	AC	15 ms	6 MB
g++-13	02_rando_large_013	AC	10 ms	4 MB
g++-13	02_rando_large_048	AC	11 ms	4 MB
g++-13	02_rando_large_054	AC	20 ms	8 MB
g++-13	02_rando_large_083	AC	14 ms	5 MB
g++-13	02_rando_large_147	AC	9 ms	4 MB
g++-13	02_rando_large_164	AC	19 ms	8 MB
g++-13	02_rando_large_227	AC	19 ms	6 MB
g++-13	02_rando_large_283	AC	23 ms	9 MB
g++-13	02_rando_large_336	AC	17 ms	7 MB
g++-13	02_rando_large_368	AC	15 ms	6 MB
g++-13	05_attack_00	AC	9 ms	4 MB
g++-13	05_attack_01	AC	7 ms	4 MB
g++-13	05_attack_mi0803_00	AC	7 ms	4 MB
g++-13	10_random_small_000	AC	9 ms	4 MB
g++-13	10_random_small_001	AC	10 ms	4 MB
g++-13	10_random_small_002	AC	10 ms	4 MB
g++-13	10_random_small_003	AC	10 ms	4 MB
g++-13	10_random_small_004	AC	10 ms	4 MB
g++-13	10_random_small_005	AC	10 ms	4 MB
g++-13	10_random_small_006	AC	10 ms	4 MB
g++-13	10_random_small_007	AC	10 ms	4 MB
g++-13	10_random_small_008	AC	10 ms	4 MB
g++-13	10_random_small_009	AC	9 ms	4 MB
g++-13	11_rando_medium_000	AC	9 ms	4 MB
g++-13	11_rando_medium_001	AC	9 ms	4 MB
g++-13	11_rando_medium_002	AC	10 ms	4 MB
g++-13	11_rando_medium_003	AC	10 ms	4 MB
g++-13	11_rando_medium_004	AC	9 ms	4 MB
g++-13	11_rando_medium_005	AC	10 ms	4 MB
g++-13	11_rando_medium_006	AC	9 ms	4 MB
g++-13	11_rando_medium_007	AC	9 ms	4 MB
g++-13	11_rando_medium_008	AC	10 ms	4 MB
g++-13	11_rando_medium_009	AC	10 ms	4 MB
g++-13	12_random_large_000	AC	241 ms	73 MB
g++-13	12_random_large_001	AC	200 ms	74 MB
g++-13	12_random_large_002	AC	545 ms	141 MB
g++-13	12_random_large_003	AC	39 ms	22 MB
g++-13	12_random_large_004	AC	329 ms	139 MB
g++-13	12_random_large_005	AC	86 ms	39 MB
g++-13	12_random_large_006	AC	404 ms	140 MB
g++-13	12_random_large_007	AC	29 ms	14 MB
g++-13	12_random_large_008	AC	170 ms	74 MB
g++-13	12_random_large_009	AC	204 ms	73 MB
g++-13	22_shortMusics_Large_000	AC	489 ms	143 MB
g++-13	22_shortMusics_Large_001	AC	408 ms	141 MB
g++-13	22_shortMusics_Large_002	AC	730 ms	276 MB
g++-13	22_shortMusics_Large_003	AC	827 ms	276 MB
g++-13	22_shortMusics_Large_004	AC	615 ms	275 MB
g++-13	22_shortMusics_Large_005	AC	756 ms	276 MB
g++-13	22_shortMusics_Large_006	AC	605 ms	277 MB
g++-13	22_shortMusics_Large_007	AC	718 ms	278 MB
g++-13	22_shortMusics_Large_008	AC	344 ms	141 MB
g++-13	22_shortMusics_Large_009	AC	491 ms	142 MB
g++-13	41_separate_medium_000	AC	9 ms	4 MB
g++-13	41_separate_medium_001	AC	9 ms	4 MB
g++-13	41_separate_medium_002	AC	9 ms	4 MB
g++-13	41_separate_medium_003	AC	9 ms	4 MB
g++-13	41_separate_medium_004	AC	8 ms	4 MB
g++-13	42_separate_large_000	AC	108 ms	70 MB
g++-13	42_separate_large_001	AC	150 ms	135 MB
g++-13	42_separate_large_002	AC	107 ms	69 MB
g++-13	42_separate_large_003	AC	192 ms	135 MB
g++-13	42_separate_large_004	AC	147 ms	136 MB
clang++-18	00_sample_00	AC	9 ms	4 MB
clang++-18	00_sample_01	AC	8 ms	4 MB
clang++-18	00_sample_02	AC	8 ms	4 MB
clang++-18	00_sample_03	AC	8 ms	4 MB
clang++-18	00_sample_04	AC	9 ms	4 MB
clang++-18	01_rando_medium_031	AC	10 ms	4 MB
clang++-18	01_rando_medium_035	AC	10 ms	4 MB
clang++-18	01_rando_medium_160	AC	10 ms	4 MB
clang++-18	01_rando_medium_278	AC	10 ms	4 MB
clang++-18	01_rando_medium_337	AC	10 ms	4 MB
clang++-18	01_rando_medium_342	AC	10 ms	4 MB
clang++-18	01_rando_medium_355	AC	9 ms	4 MB
clang++-18	01_rando_medium_452	AC	10 ms	4 MB
clang++-18	01_rando_medium_467	AC	10 ms	4 MB
clang++-18	01_rando_medium_665	AC	10 ms	4 MB
clang++-18	02_rando_large_000	AC	17 ms	6 MB
clang++-18	02_rando_large_013	AC	10 ms	4 MB
clang++-18	02_rando_large_048	AC	11 ms	4 MB
clang++-18	02_rando_large_054	AC	24 ms	9 MB
clang++-18	02_rando_large_083	AC	15 ms	5 MB
clang++-18	02_rando_large_147	AC	10 ms	4 MB
clang++-18	02_rando_large_164	AC	21 ms	8 MB
clang++-18	02_rando_large_227	AC	20 ms	6 MB
clang++-18	02_rando_large_283	AC	24 ms	8 MB
clang++-18	02_rando_large_336	AC	20 ms	6 MB
clang++-18	02_rando_large_368	AC	16 ms	7 MB
clang++-18	05_attack_00	AC	9 ms	4 MB
clang++-18	05_attack_01	AC	8 ms	4 MB
clang++-18	05_attack_mi0803_00	AC	10 ms	4 MB
clang++-18	10_random_small_000	AC	9 ms	4 MB
clang++-18	10_random_small_001	AC	9 ms	4 MB
clang++-18	10_random_small_002	AC	10 ms	4 MB
clang++-18	10_random_small_003	AC	10 ms	4 MB
clang++-18	10_random_small_004	AC	10 ms	4 MB
clang++-18	10_random_small_005	AC	10 ms	4 MB
clang++-18	10_random_small_006	AC	9 ms	4 MB
clang++-18	10_random_small_007	AC	12 ms	4 MB
clang++-18	10_random_small_008	AC	10 ms	4 MB
clang++-18	10_random_small_009	AC	8 ms	4 MB
clang++-18	11_rando_medium_000	AC	9 ms	4 MB
clang++-18	11_rando_medium_001	AC	9 ms	4 MB
clang++-18	11_rando_medium_002	AC	9 ms	4 MB
clang++-18	11_rando_medium_003	AC	9 ms	4 MB
clang++-18	11_rando_medium_004	AC	10 ms	4 MB
clang++-18	11_rando_medium_005	AC	9 ms	4 MB
clang++-18	11_rando_medium_006	AC	9 ms	4 MB
clang++-18	11_rando_medium_007	AC	10 ms	4 MB
clang++-18	11_rando_medium_008	AC	10 ms	4 MB
clang++-18	11_rando_medium_009	AC	9 ms	4 MB
clang++-18	12_random_large_000	AC	265 ms	72 MB
clang++-18	12_random_large_001	AC	238 ms	73 MB
clang++-18	12_random_large_002	AC	658 ms	141 MB
clang++-18	12_random_large_003	AC	43 ms	22 MB
clang++-18	12_random_large_004	AC	377 ms	138 MB
clang++-18	12_random_large_005	AC	96 ms	39 MB
clang++-18	12_random_large_006	AC	472 ms	140 MB
clang++-18	12_random_large_007	AC	34 ms	15 MB
clang++-18	12_random_large_008	AC	203 ms	74 MB
clang++-18	12_random_large_009	AC	233 ms	72 MB
clang++-18	22_shortMusics_Large_000	AC	565 ms	142 MB
clang++-18	22_shortMusics_Large_001	AC	473 ms	141 MB
clang++-18	22_shortMusics_Large_002	AC	856 ms	276 MB
clang++-18	22_shortMusics_Large_003	AC	956 ms	277 MB
clang++-18	22_shortMusics_Large_004	AC	705 ms	275 MB
clang++-18	22_shortMusics_Large_005	AC	863 ms	277 MB
clang++-18	22_shortMusics_Large_006	AC	820 ms	276 MB
clang++-18	22_shortMusics_Large_007	AC	823 ms	278 MB
clang++-18	22_shortMusics_Large_008	AC	403 ms	141 MB
clang++-18	22_shortMusics_Large_009	AC	565 ms	142 MB
clang++-18	41_separate_medium_000	AC	9 ms	4 MB
clang++-18	41_separate_medium_001	AC	9 ms	4 MB
clang++-18	41_separate_medium_002	AC	9 ms	4 MB
clang++-18	41_separate_medium_003	AC	9 ms	4 MB
clang++-18	41_separate_medium_004	AC	9 ms	4 MB
clang++-18	42_separate_large_000	AC	127 ms	69 MB
clang++-18	42_separate_large_001	AC	177 ms	135 MB
clang++-18	42_separate_large_002	AC	126 ms	71 MB
clang++-18	42_separate_large_003	AC	225 ms	137 MB
clang++-18	42_separate_large_004	AC	173 ms	136 MB

Back to top page