結果
問題 | No.2332 Make a Sequence |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:05:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 6,462 bytes |
コンパイル時間 | 1,623 ms |
コンパイル使用メモリ | 131,628 KB |
最終ジャッジ日時 | 2025-02-13 10:46:26 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
ソースコード
#ifndef LOCAL#define FAST_IO#endif// ============#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cmath>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define OVERRIDE(a, b, c, d, ...) d#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)#define ALL(x) begin(x), end(x)using namespace std;using u32 = unsigned int;using u64 = unsigned long long;using i32 = signed int;using i64 = signed long long;using f64 = double;using f80 = long double;template <typename T>using Vec = vector<T>;template <typename T>bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}template <typename T>Vec<tuple<i32, i32, T>> runlength(const Vec<T> &a) {if (a.empty()) {return Vec<tuple<i32, i32, T>>();}Vec<tuple<i32, i32, T>> ret;i32 prv = 0;REP(i, 1, a.size()) {if (a[i - 1] != a[i]) {ret.emplace_back(prv, i, a[i - 1]);prv = i;}}ret.emplace_back(prv, (i32)a.size(), a.back());return ret;}#ifdef INT128using u128 = __uint128_t;using i128 = __int128_t;istream &operator>>(istream &is, i128 &x) {i64 v;is >> v;x = v;return is;}ostream &operator<<(ostream &os, i128 x) {os << (i64)x;return os;}istream &operator>>(istream &is, u128 &x) {u64 v;is >> v;x = v;return is;}ostream &operator<<(ostream &os, u128 x) {os << (u64)x;return os;}#endif[[maybe_unused]] constexpr i32 INF = 1000000100;[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;struct SetUpIO {SetUpIO() {#ifdef FAST_IOios::sync_with_stdio(false);cin.tie(nullptr);#endifcout << fixed << setprecision(15);}} set_up_io;// ============#ifdef DEBUGF#else#define DBG(x) (void)0#endif// ============#include <vector>template <typename Cont>std::vector<int> z_algorithm(const Cont &s) {if (s.empty()) {return std::vector<int>(0);}std::vector<int> z(s.size());z[0] = (int) s.size();int i = 1, j = 0;while (i < (int) s.size()) {while (i + j < (int) s.size() && s[i + j] == s[j]) {++j;}z[i] = j;if (j == 0) {++i;continue;}int k = 1;while (k < j && k + z[k] < j) {z[i + k] = z[k];++k;}i += k;j -= k;}return z;}// ============// https://ei1333.github.io/library/structure/convex-hull-trick/dynamic-li-chao-tree.hpp/*** @brief Dynamic-Li-Chao-Tree* @docs docs/dynamic-li-chao-tree.md*/template< typename T, T x_low, T x_high, T id >struct DynamicLiChaoTree {struct Line {T a, b;Line(T a, T b) : a(a), b(b) {}inline T get(T x) const { return a * x + b; }};struct Node {Line x;Node *l, *r;Node(const Line &x) : x{x}, l{nullptr}, r{nullptr} {}};Node *root;DynamicLiChaoTree() : root{nullptr} {}Node *add_line(Node *t, Line &x, const T &l, const T &r, const T &x_l, const T &x_r) {if(!t) return new Node(x);T t_l = t->x.get(l), t_r = t->x.get(r);if(t_l <= x_l && t_r <= x_r) {return t;} else if(t_l >= x_l && t_r >= x_r) {t->x = x;return t;} else {T m = (l + r) / 2;if(m == r) --m;T t_m = t->x.get(m), x_m = x.get(m);if(t_m > x_m) {swap(t->x, x);if(x_l >= t_l) t->l = add_line(t->l, x, l, m, t_l, t_m);else t->r = add_line(t->r, x, m + 1, r, t_m + x.a, t_r);} else {if(t_l >= x_l) t->l = add_line(t->l, x, l, m, x_l, x_m);else t->r = add_line(t->r, x, m + 1, r, x_m + x.a, x_r);}return t;}}void add_line(const T &a, const T &b) {Line x(a, b);root = add_line(root, x, x_low, x_high, x.get(x_low), x.get(x_high));}Node *add_segment(Node *t, Line &x, const T &a, const T &b, const T &l, const T &r, const T &x_l, const T &x_r) {if(r < a || b < l) return t;if(a <= l && r <= b) {Line y{x};return add_line(t, y, l, r, x_l, x_r);}if(t) {T t_l = t->x.get(l), t_r = t->x.get(r);if(t_l <= x_l && t_r <= x_r) return t;} else {t = new Node(Line(0, id));}T m = (l + r) / 2;if(m == r) --m;T x_m = x.get(m);t->l = add_segment(t->l, x, a, b, l, m, x_l, x_m);t->r = add_segment(t->r, x, a, b, m + 1, r, x_m + x.a, x_r);return t;}void add_segment(const T &l, const T &r, const T &a, const T &b) {Line x(a, b);root = add_segment(root, x, l, r - 1, x_low, x_high, x.get(x_low), x.get(x_high));}T query(const Node *t, const T &l, const T &r, const T &x) const {if(!t) return id;if(l == r) return t->x.get(x);T m = (l + r) / 2;if(m == r) --m;if(x <= m) return min(t->x.get(x), query(t->l, l, m, x));else return min(t->x.get(x), query(t->r, m + 1, r, x));}T query(const T &x) const {return query(root, x_low, x_high, x);}};int main() {i32 n, m;cin >> n >> m;Vec<i32> a(n), b(m);Vec<i64> c(m);REP(i, n) {cin >> a[i];}REP(i, m) {cin >> b[i];}REP(i, m) {cin >> c[i];}Vec<i32> conc(n + m + 1);REP(i, n) {conc[i] = a[i];}conc[n] = -1;REP(i, m) {conc[n + 1 + i] = b[i];}Vec<i32> z = z_algorithm(conc);z.erase(z.begin(), z.begin() + (n + 1));DynamicLiChaoTree<i64, -1, 1000000, INF64> lct;lct.add_segment(0, 1, 0, 0);REP(i, m) {i64 dp = lct.query(i);if (z[i] != 0) {lct.add_segment(i + 1, i + z[i] + 1, c[i], dp - i * c[i]);}}i64 ans = lct.query(m);if (ans == INF64) {cout << -1 << '\n';} else {cout << ans << '\n';}}