test/aoj/2725.CHT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2725
• Link: View error logs on GitHub Actions

Depends on

• Convex-Hull-Trick (src/Optimization/ConvexHullTrick.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2725
// competitive-verifier: TLE 2
// competitive-verifier: MLE 64
#include <iostream>
#include <numeric>
#include "src/Optimization/ConvexHullTrick.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 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]; });
 ConvexHullTrick<long long, MAXIMIZE> cht[T + 1];
 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) {
   long long val= p[I];
   if (!cht[x - ti].empty()) val= max(val, cht[x - ti].query(f[I]) + p[I] - f[I] * f[I]);
   ans= max(ans, val);
   cht[x].insert(2 * f[I], val - f[I] * f[I]);
  }
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/2725.CHT.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2725
// competitive-verifier: TLE 2
// competitive-verifier: MLE 64
#include <iostream>
#include <numeric>
#line 2 "src/Optimization/ConvexHullTrick.hpp"
#include <limits>
#include <algorithm>
#include <set>
#include <array>
#include <cassert>
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 8 "src/Optimization/ConvexHullTrick.hpp"
template <typename T, MinMaxEnum obj= MINIMIZE> class ConvexHullTrick {
 struct Line {
  T k, m;
  mutable T p;
  bool operator<(const Line &o) const { return k < o.k; }
  bool operator<(T x) const { return p < x; }
 };
 static constexpr T INF= std::numeric_limits<T>::max();
 static T lc_div(T a, T b) {
  if constexpr (std::is_integral_v<T>) return a / b - ((a ^ b) < 0 && a % b);
  else return a / b;
 }
 using ms= std::multiset<Line, std::less<>>;
 ms ls;
 bool insect(typename ms::iterator x, typename ms::iterator y) {
  if (y == ls.end()) return x->p= INF, false;
  if (x->k == y->k) x->p= (x->m > y->m ? INF : -INF);
  else x->p= lc_div(y->m - x->m, x->k - y->k);
  return x->p >= y->p;
 }
public:
 void insert(T k, T m) {
  if constexpr (obj == MINIMIZE) k= -k, m= -m;
  auto z= ls.insert({k, m, 0}), y= z++, x= y;
  while (insect(y, z)) z= ls.erase(z);
  if (x != ls.begin() && insect(--x, y)) insect(x, y= ls.erase(y));
  while ((y= x) != ls.begin() && (--x)->p >= y->p) insect(x, ls.erase(y));
 }
 bool empty() const { return ls.empty(); }
 std::array<T, 2> query_line(T x) const {
  assert(!ls.empty());
  auto l= ls.lower_bound(x);
  if constexpr (obj == MINIMIZE) return {-l->k, -l->m};
  else return {l->k, l->m};
 }
 T query(T x) const {
  auto [k, m]= query_line(x);
  return k * x + m;
 }
};
template <typename T> class ConvexHullTrick_XY {
 ConvexHullTrick<long double, MINIMIZE> cht_mn;
 ConvexHullTrick<long double, MAXIMIZE> cht_mx;
 T amx= std::numeric_limits<T>::lowest(), amn= std::numeric_limits<T>::max();
public:
 void insert(T a, T b) { cht_mn.insert(a, b), cht_mx.insert(a, b), amn= std::min(amn, a), amx= std::max(amx, a); }
 bool empty() const { return cht_mn.empty(); }
 T get_max(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::max(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mx.query_line(z) : cht_mn.query_line(z);
  return T(a) * x + T(b) * y;
 }
 T get_min(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::min(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mn.query_line(z) : cht_mx.query_line(z);
  return T(a) * x + T(b) * y;
 }
};
#line 7 "test/aoj/2725.CHT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 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]; });
 ConvexHullTrick<long long, MAXIMIZE> cht[T + 1];
 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) {
   long long val= p[I];
   if (!cht[x - ti].empty()) val= max(val, cht[x - ti].query(f[I]) + p[I] - f[I] * f[I]);
   ans= max(ans, val);
   cht[x].insert(2 * f[I], val - f[I] * f[I]);
  }
 }
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00	AC	9 ms	4 MB
g++-13	00_sample_01	AC	9 ms	4 MB
g++-13	00_sample_02	AC	9 ms	4 MB
g++-13	00_sample_03	AC	9 ms	3 MB
g++-13	00_sample_04	AC	8 ms	3 MB
g++-13	01_rando_medium_031	AC	10 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	10 ms	3 MB
g++-13	01_rando_medium_342	AC	10 ms	3 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	3 MB
g++-13	02_rando_large_000	AC	15 ms	4 MB
g++-13	02_rando_large_013	AC	10 ms	4 MB
g++-13	02_rando_large_048	AC	12 ms	4 MB
g++-13	02_rando_large_054	AC	22 ms	4 MB
g++-13	02_rando_large_083	AC	14 ms	4 MB
g++-13	02_rando_large_147	AC	12 ms	4 MB
g++-13	02_rando_large_164	AC	21 ms	4 MB
g++-13	02_rando_large_227	AC	19 ms	4 MB
g++-13	02_rando_large_283	AC	25 ms	4 MB
g++-13	02_rando_large_336	AC	18 ms	4 MB
g++-13	02_rando_large_368	AC	16 ms	4 MB
g++-13	05_attack_00	AC	9 ms	4 MB
g++-13	05_attack_01	AC	9 ms	4 MB
g++-13	05_attack_mi0803_00	AC	9 ms	4 MB
g++-13	10_random_small_000	AC	9 ms	3 MB
g++-13	10_random_small_001	AC	9 ms	4 MB
g++-13	10_random_small_002	AC	9 ms	4 MB
g++-13	10_random_small_003	AC	9 ms	4 MB
g++-13	10_random_small_004	AC	9 ms	4 MB
g++-13	10_random_small_005	AC	9 ms	4 MB
g++-13	10_random_small_006	AC	9 ms	4 MB
g++-13	10_random_small_007	AC	9 ms	4 MB
g++-13	10_random_small_008	AC	9 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	9 ms	4 MB
g++-13	11_rando_medium_003	AC	9 ms	4 MB
g++-13	11_rando_medium_004	AC	9 ms	4 MB
g++-13	11_rando_medium_005	AC	9 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	9 ms	4 MB
g++-13	12_random_large_000	AC	309 ms	6 MB
g++-13	12_random_large_001	AC	287 ms	7 MB
g++-13	12_random_large_002	AC	869 ms	8 MB
g++-13	12_random_large_003	AC	55 ms	6 MB
g++-13	12_random_large_004	AC	556 ms	7 MB
g++-13	12_random_large_005	AC	115 ms	6 MB
g++-13	12_random_large_006	AC	621 ms	7 MB
g++-13	12_random_large_007	AC	34 ms	5 MB
g++-13	12_random_large_008	AC	239 ms	7 MB
g++-13	12_random_large_009	AC	248 ms	6 MB
g++-13	22_shortMusics_Large_000	AC	938 ms	9 MB
g++-13	22_shortMusics_Large_001	AC	832 ms	8 MB
g++-13	22_shortMusics_Large_002	AC	1694 ms	10 MB
g++-13	22_shortMusics_Large_003	AC	1709 ms	10 MB
g++-13	22_shortMusics_Large_004	AC	1281 ms	9 MB
g++-13	22_shortMusics_Large_005	AC	1698 ms	10 MB
g++-13	22_shortMusics_Large_006	AC	1079 ms	10 MB
g++-13	22_shortMusics_Large_007	AC	1404 ms	11 MB
g++-13	22_shortMusics_Large_008	AC	672 ms	8 MB
g++-13	22_shortMusics_Large_009	AC	924 ms	9 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	8 ms	4 MB
g++-13	41_separate_medium_004	AC	8 ms	4 MB
g++-13	42_separate_large_000	AC	177 ms	5 MB
g++-13	42_separate_large_001	AC	256 ms	6 MB
g++-13	42_separate_large_002	AC	186 ms	5 MB
g++-13	42_separate_large_003	AC	331 ms	5 MB
g++-13	42_separate_large_004	AC	236 ms	5 MB
clang++-18	00_sample_00	AC	9 ms	4 MB
clang++-18	00_sample_01	AC	9 ms	4 MB
clang++-18	00_sample_02	AC	9 ms	4 MB
clang++-18	00_sample_03	AC	9 ms	4 MB
clang++-18	00_sample_04	AC	10 ms	4 MB
clang++-18	01_rando_medium_031	AC	9 ms	4 MB
clang++-18	01_rando_medium_035	AC	9 ms	4 MB
clang++-18	01_rando_medium_160	AC	9 ms	4 MB
clang++-18	01_rando_medium_278	AC	9 ms	4 MB
clang++-18	01_rando_medium_337	AC	9 ms	4 MB
clang++-18	01_rando_medium_342	AC	9 ms	4 MB
clang++-18	01_rando_medium_355	AC	9 ms	4 MB
clang++-18	01_rando_medium_452	AC	9 ms	4 MB
clang++-18	01_rando_medium_467	AC	9 ms	4 MB
clang++-18	01_rando_medium_665	AC	9 ms	4 MB
clang++-18	02_rando_large_000	AC	15 ms	4 MB
clang++-18	02_rando_large_013	AC	10 ms	4 MB
clang++-18	02_rando_large_048	AC	12 ms	4 MB
clang++-18	02_rando_large_054	AC	22 ms	4 MB
clang++-18	02_rando_large_083	AC	15 ms	4 MB
clang++-18	02_rando_large_147	AC	10 ms	4 MB
clang++-18	02_rando_large_164	AC	22 ms	4 MB
clang++-18	02_rando_large_227	AC	19 ms	4 MB
clang++-18	02_rando_large_283	AC	25 ms	4 MB
clang++-18	02_rando_large_336	AC	18 ms	4 MB
clang++-18	02_rando_large_368	AC	16 ms	4 MB
clang++-18	05_attack_00	AC	9 ms	4 MB
clang++-18	05_attack_01	AC	9 ms	4 MB
clang++-18	05_attack_mi0803_00	AC	9 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	9 ms	4 MB
clang++-18	10_random_small_003	AC	9 ms	4 MB
clang++-18	10_random_small_004	AC	8 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	9 ms	4 MB
clang++-18	10_random_small_008	AC	9 ms	4 MB
clang++-18	10_random_small_009	AC	9 ms	4 MB
clang++-18	11_rando_medium_000	AC	10 ms	4 MB
clang++-18	11_rando_medium_001	AC	9 ms	4 MB
clang++-18	11_rando_medium_002	AC	10 ms	4 MB
clang++-18	11_rando_medium_003	AC	10 ms	4 MB
clang++-18	11_rando_medium_004	AC	9 ms	4 MB
clang++-18	11_rando_medium_005	AC	9 ms	4 MB
clang++-18	11_rando_medium_006	AC	10 ms	4 MB
clang++-18	11_rando_medium_007	AC	9 ms	4 MB
clang++-18	11_rando_medium_008	AC	9 ms	4 MB
clang++-18	11_rando_medium_009	AC	9 ms	4 MB
clang++-18	12_random_large_000	AC	335 ms	6 MB
clang++-18	12_random_large_001	AC	311 ms	7 MB
clang++-18	12_random_large_002	AC	903 ms	8 MB
clang++-18	12_random_large_003	AC	57 ms	6 MB
clang++-18	12_random_large_004	AC	598 ms	7 MB
clang++-18	12_random_large_005	AC	124 ms	6 MB
clang++-18	12_random_large_006	AC	676 ms	7 MB
clang++-18	12_random_large_007	AC	36 ms	5 MB
clang++-18	12_random_large_008	AC	253 ms	7 MB
clang++-18	12_random_large_009	AC	272 ms	6 MB
clang++-18	22_shortMusics_Large_000	AC	1068 ms	9 MB
clang++-18	22_shortMusics_Large_001	AC	970 ms	8 MB
clang++-18	22_shortMusics_Large_002	AC	1902 ms	10 MB
clang++-18	22_shortMusics_Large_003	TLE	2009 ms	0 MB
clang++-18	22_shortMusics_Large_004	AC	1418 ms	8 MB
clang++-18	22_shortMusics_Large_005	AC	1865 ms	10 MB
clang++-18	22_shortMusics_Large_006	AC	1216 ms	10 MB
clang++-18	22_shortMusics_Large_007	AC	1659 ms	11 MB
clang++-18	22_shortMusics_Large_008	AC	785 ms	8 MB
clang++-18	22_shortMusics_Large_009	AC	1057 ms	9 MB
clang++-18	41_separate_medium_000	AC	10 ms	4 MB
clang++-18	41_separate_medium_001	AC	10 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	181 ms	5 MB
clang++-18	42_separate_large_001	AC	261 ms	6 MB
clang++-18	42_separate_large_002	AC	190 ms	5 MB
clang++-18	42_separate_large_003	AC	333 ms	5 MB
clang++-18	42_separate_large_004	AC	243 ms	5 MB

Back to top page