test/yukicoder/1297.CHT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/1297

Depends on

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

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1297
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <array>
#include <algorithm>
#include "src/Optimization/ConvexHullTrick.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 ConvexHullTrick<long long, MINIMIZE> cht1, cht2;
 long long N, C;
 cin >> N >> C;
 cht1.insert(0, 0);
 for (long long i= 1;; ++i) {
  long long a, b, c= C * 2 * i;
  cin >> a >> b, a+= a, b+= b;
  cht2.insert(a - c, cht1.query(-a - c) + c * (i - 1) + b);
  if (i == N) break;
  cht1.insert(i, cht2.query(i) + c * (i + 1));
 }
 cout << (cht2.query(N) + (N + 1) * N * C) / 2 << '\n';
 return 0;
}

#line 1 "test/yukicoder/1297.CHT.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1297
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <array>
#include <algorithm>
#line 2 "src/Optimization/ConvexHullTrick.hpp"
#include <limits>
#line 4 "src/Optimization/ConvexHullTrick.hpp"
#include <set>
#line 6 "src/Optimization/ConvexHullTrick.hpp"
#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 8 "test/yukicoder/1297.CHT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 ConvexHullTrick<long long, MINIMIZE> cht1, cht2;
 long long N, C;
 cin >> N >> C;
 cht1.insert(0, 0);
 for (long long i= 1;; ++i) {
  long long a, b, c= C * 2 * i;
  cin >> a >> b, a+= a, b+= b;
  cht2.insert(a - c, cht1.query(-a - c) + c * (i - 1) + b);
  if (i == N) break;
  cht1.insert(i, cht2.query(i) + c * (i + 1));
 }
 cout << (cht2.query(N) + (N + 1) * N * C) / 2 << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	01_sample_01.txt	AC	7 ms	3 MB
g++-13	01_sample_02.txt	AC	6 ms	4 MB
g++-13	02_small_01.txt	AC	6 ms	4 MB
g++-13	02_small_02.txt	AC	6 ms	4 MB
g++-13	02_small_03.txt	AC	6 ms	4 MB
g++-13	02_small_04.txt	AC	6 ms	4 MB
g++-13	02_small_05.txt	AC	7 ms	4 MB
g++-13	02_small_06.txt	AC	8 ms	4 MB
g++-13	02_small_07.txt	AC	8 ms	4 MB
g++-13	03_max.txt	AC	65 ms	16 MB
g++-13	03_min.txt	AC	76 ms	16 MB
g++-13	03_rnd_01.txt	AC	43 ms	7 MB
g++-13	03_rnd_02.txt	AC	45 ms	7 MB
g++-13	03_rnd_03.txt	AC	52 ms	14 MB
g++-13	03_smallA_01.txt	AC	43 ms	7 MB
g++-13	03_smallA_02.txt	AC	45 ms	7 MB
g++-13	03_smallA_03.txt	AC	47 ms	7 MB
g++-13	03_smallB_01.txt	AC	41 ms	7 MB
g++-13	03_smallB_02.txt	AC	42 ms	7 MB
g++-13	03_smallB_03.txt	AC	78 ms	16 MB
g++-13	03_smallD_01.txt	AC	32 ms	4 MB
g++-13	03_smallD_02.txt	AC	31 ms	3 MB
g++-13	03_smallD_03.txt	AC	41 ms	7 MB
clang++-18	01_sample_01.txt	AC	7 ms	4 MB
clang++-18	01_sample_02.txt	AC	6 ms	4 MB
clang++-18	02_small_01.txt	AC	6 ms	4 MB
clang++-18	02_small_02.txt	AC	6 ms	4 MB
clang++-18	02_small_03.txt	AC	6 ms	4 MB
clang++-18	02_small_04.txt	AC	6 ms	4 MB
clang++-18	02_small_05.txt	AC	8 ms	4 MB
clang++-18	02_small_06.txt	AC	9 ms	4 MB
clang++-18	02_small_07.txt	AC	8 ms	4 MB
clang++-18	03_max.txt	AC	67 ms	16 MB
clang++-18	03_min.txt	AC	88 ms	16 MB
clang++-18	03_rnd_01.txt	AC	49 ms	7 MB
clang++-18	03_rnd_02.txt	AC	54 ms	7 MB
clang++-18	03_rnd_03.txt	AC	64 ms	14 MB
clang++-18	03_smallA_01.txt	AC	46 ms	7 MB
clang++-18	03_smallA_02.txt	AC	49 ms	7 MB
clang++-18	03_smallA_03.txt	AC	51 ms	7 MB
clang++-18	03_smallB_01.txt	AC	47 ms	7 MB
clang++-18	03_smallB_02.txt	AC	48 ms	7 MB
clang++-18	03_smallB_03.txt	AC	91 ms	16 MB
clang++-18	03_smallD_01.txt	AC	32 ms	4 MB
clang++-18	03_smallD_02.txt	AC	31 ms	4 MB
clang++-18	03_smallD_03.txt	AC	48 ms	7 MB

Back to top page