test/yukicoder/2012.test.cpp

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

Depends on

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

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2012
// competitive-verifier: TLE 0.5
// 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);
 int N;
 cin >> N;
 ConvexHullTrick_XY<long long> cht;
 int x[N], y[N];
 for (int i= 0; i < N; ++i) cin >> x[i] >> y[i], cht.insert(x[i], -y[i]);
 long long ans= 0;
 for (int i= N; i--;) ans= max(ans, cht.get_max(y[i], x[i]));
 cout << ans << '\n';
 return 0;
}

#line 1 "test/yukicoder/2012.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2012
// competitive-verifier: TLE 0.5
// 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/2012.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 ConvexHullTrick_XY<long long> cht;
 int x[N], y[N];
 for (int i= 0; i < N; ++i) cin >> x[i] >> y[i], cht.insert(x[i], -y[i]);
 long long ans= 0;
 for (int i= N; i--;) ans= max(ans, cht.get_max(y[i], x[i]));
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	01_sample_01.txt	AC	6 ms	4 MB
g++-13	02_small_01.txt	AC	5 ms	4 MB
g++-13	02_small_02.txt	AC	5 ms	3 MB
g++-13	02_small_03.txt	AC	5 ms	4 MB
g++-13	02_small_04.txt	AC	5 ms	4 MB
g++-13	02_small_05.txt	AC	5 ms	4 MB
g++-13	02_small_06.txt	AC	5 ms	4 MB
g++-13	02_small_07.txt	AC	5 ms	3 MB
g++-13	02_small_08.txt	AC	5 ms	3 MB
g++-13	02_small_09.txt	AC	5 ms	4 MB
g++-13	02_small_10.txt	AC	5 ms	4 MB
g++-13	02_small_11.txt	AC	5 ms	4 MB
g++-13	02_small_12.txt	AC	5 ms	4 MB
g++-13	02_small_13.txt	AC	5 ms	4 MB
g++-13	02_small_14.txt	AC	5 ms	4 MB
g++-13	02_small_15.txt	AC	5 ms	4 MB
g++-13	03_large_01.txt	AC	65 ms	5 MB
g++-13	03_large_02.txt	AC	67 ms	5 MB
g++-13	03_large_03.txt	AC	67 ms	5 MB
g++-13	03_large_04.txt	AC	66 ms	5 MB
g++-13	03_large_05.txt	AC	67 ms	5 MB
g++-13	03_large_06.txt	AC	67 ms	5 MB
g++-13	03_large_07.txt	AC	68 ms	5 MB
g++-13	03_large_08.txt	AC	66 ms	5 MB
g++-13	03_large_09.txt	AC	66 ms	5 MB
g++-13	03_large_10.txt	AC	66 ms	5 MB
g++-13	04_circle_01.txt	AC	180 ms	6 MB
g++-13	04_circle_02.txt	AC	175 ms	6 MB
g++-13	04_circle_03.txt	AC	178 ms	6 MB
g++-13	04_circle_04.txt	AC	177 ms	6 MB
g++-13	04_circle_05.txt	AC	179 ms	6 MB
g++-13	04_circle_06.txt	AC	83 ms	5 MB
g++-13	04_circle_07.txt	AC	83 ms	5 MB
g++-13	04_circle_08.txt	AC	83 ms	5 MB
g++-13	04_circle_09.txt	AC	83 ms	5 MB
g++-13	04_circle_10.txt	AC	83 ms	5 MB
g++-13	05_manual_01.txt	AC	7 ms	4 MB
g++-13	05_manual_02.txt	AC	6 ms	4 MB
g++-13	05_manual_03.txt	AC	6 ms	4 MB
g++-13	05_manual_04.txt	AC	6 ms	4 MB
g++-13	05_manual_05.txt	AC	6 ms	4 MB
g++-13	98_challenge01.txt	AC	37 ms	9 MB
clang++-18	01_sample_01.txt	AC	6 ms	4 MB
clang++-18	02_small_01.txt	AC	5 ms	4 MB
clang++-18	02_small_02.txt	AC	5 ms	4 MB
clang++-18	02_small_03.txt	AC	5 ms	4 MB
clang++-18	02_small_04.txt	AC	6 ms	4 MB
clang++-18	02_small_05.txt	AC	6 ms	4 MB
clang++-18	02_small_06.txt	AC	6 ms	4 MB
clang++-18	02_small_07.txt	AC	5 ms	4 MB
clang++-18	02_small_08.txt	AC	5 ms	4 MB
clang++-18	02_small_09.txt	AC	5 ms	4 MB
clang++-18	02_small_10.txt	AC	5 ms	4 MB
clang++-18	02_small_11.txt	AC	5 ms	4 MB
clang++-18	02_small_12.txt	AC	5 ms	4 MB
clang++-18	02_small_13.txt	AC	5 ms	4 MB
clang++-18	02_small_14.txt	AC	5 ms	4 MB
clang++-18	02_small_15.txt	AC	5 ms	4 MB
clang++-18	03_large_01.txt	AC	77 ms	5 MB
clang++-18	03_large_02.txt	AC	80 ms	5 MB
clang++-18	03_large_03.txt	AC	81 ms	5 MB
clang++-18	03_large_04.txt	AC	77 ms	5 MB
clang++-18	03_large_05.txt	AC	79 ms	5 MB
clang++-18	03_large_06.txt	AC	81 ms	5 MB
clang++-18	03_large_07.txt	AC	81 ms	5 MB
clang++-18	03_large_08.txt	AC	80 ms	5 MB
clang++-18	03_large_09.txt	AC	79 ms	5 MB
clang++-18	03_large_10.txt	AC	79 ms	5 MB
clang++-18	04_circle_01.txt	AC	212 ms	6 MB
clang++-18	04_circle_02.txt	AC	184 ms	6 MB
clang++-18	04_circle_03.txt	AC	185 ms	6 MB
clang++-18	04_circle_04.txt	AC	185 ms	6 MB
clang++-18	04_circle_05.txt	AC	187 ms	6 MB
clang++-18	04_circle_06.txt	AC	104 ms	5 MB
clang++-18	04_circle_07.txt	AC	104 ms	5 MB
clang++-18	04_circle_08.txt	AC	106 ms	5 MB
clang++-18	04_circle_09.txt	AC	104 ms	5 MB
clang++-18	04_circle_10.txt	AC	105 ms	5 MB
clang++-18	05_manual_01.txt	AC	7 ms	4 MB
clang++-18	05_manual_02.txt	AC	6 ms	4 MB
clang++-18	05_manual_03.txt	AC	6 ms	4 MB
clang++-18	05_manual_04.txt	AC	6 ms	4 MB
clang++-18	05_manual_05.txt	AC	6 ms	4 MB
clang++-18	98_challenge01.txt	AC	49 ms	9 MB

Back to top page