結果
問題 | No.2332 Make a Sequence |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:16:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 6,382 bytes |
コンパイル時間 | 2,452 ms |
コンパイル使用メモリ | 160,936 KB |
最終ジャッジ日時 | 2025-02-13 12:53:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:210:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 210 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:212:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 212 | rep(i, n) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:213:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 213 | rep(i, m) scanf("%d", &b[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:215:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 215 | rep(i, m) scanf("%lld", &c[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <string.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <ciso646>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define REP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME#define REP3(i, l, r, s) \for (int i = int(l), rep3_r = int(r), rep3_s = int(s); i < rep3_r; \i += rep3_s)#define REP2(i, l, r) REP3(i, l, r, 1)#define REP1(i, n) REP2(i, 0, n)#define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1, )(__VA_ARGS__)#define repin(i, l, r) for (int i = int(l), repin_r = int(r); i <= repin_r; ++i)#define RREP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME#define RREP3(i, l, r, s) \for (int i = int(r) - 1, rrep3_l = int(l), rrep3_s = int(s); i >= rrep3_l; \i -= rrep3_s)#define RREP2(i, l, r) RREP3(i, l, r, 1)#define RREP1(i, n) RREP2(i, 0, n)#define rrep(...) RREP_OVERLOAD(__VA_ARGS__, RREP3, RREP2, RREP1, )(__VA_ARGS__)#define rrepin(i, l, r) \for (int i = int(r), rrepin_l = int(l); i >= rrepin_l; --i)#define fi first#define se second#include <atcoder/string>#include <algorithm>#include <cassert>#include <vector>namespace rklib {template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <class T>bool chmin_non_negative(T &a, const T &b) {if (a < 0 || a > b) {a = b;return true;}return false;}template <class T>T div_floor(T num, T den) {if (den < 0) num = -num, den = -den;return num >= 0 ? num / den : (num + 1) / den - 1;}template <class T>T div_ceil(T num, T den) {if (den < 0) num = -num, den = -den;return num <= 0 ? num / den : (num - 1) / den + 1;}} // namespace rklibusing namespace std;using namespace rklib;using lint = long long;using pii = pair<int, int>;using pll = pair<lint, lint>;template <typename T, T inf>class LiChaoTree {public:LiChaoTree() = default;explicit LiChaoTree(const std::vector<T>& x) : xs(x) {std::sort(xs.begin(), xs.end());xs.erase(std::unique(xs.begin(), xs.end()), xs.end());n = (int)xs.size();sz = 1;while (sz < n) sz <<= 1;while ((int)xs.size() < sz) xs.emplace_back(xs.back() + 1);node.resize(sz * 2, Line(T(0), inf));}// 直線 ax + b を追加void add_line(T a, T b) { update(a, b, 0, sz, 1); }// 線分 ax + b (x_l <= x < x_r) を追加void add_segment(T a, T b, T x_l, T x_r) {int l = std::lower_bound(xs.begin(), xs.end(), x_l) - xs.begin();int r = std::lower_bound(xs.begin(), xs.end(), x_r) - xs.begin();l += sz;r += sz;int width = 1, seg_idx_left = sz;while (l < r) {if (l & 1) {int L = (l - seg_idx_left) * width;int R = L + width;update(a, b, L, R, l);l++;}if (r & 1) {r--;int L = (r - seg_idx_left) * width;int R = L + width;update(a, b, L, R, r);}l >>= 1;r >>= 1;width <<= 1;seg_idx_left >>= 1;}}// min_{i} (a_i * x + b) を求めるT get_min(T x) {int pos = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();assert(0 <= pos and pos < sz);pos += sz;T ret = node[pos].eval(x);while (pos > 1) {pos >>= 1;ret = std::min(ret, node[pos].eval(x));}return ret;}private:struct Line {T a, b;Line(T a, T b) : a(a), b(b) {}inline T eval(T x) const { return (a * x + b); }};std::vector<T> xs;std::vector<Line> node;int n, sz;void update(T a, T b, int l, int r, int pos) {Line new_line(a, b);while (1) {bool is_over_l = (new_line.eval(xs[l]) >= node[pos].eval(xs[l]));bool is_over_r =(new_line.eval(xs[r - 1]) >= node[pos].eval(xs[r - 1]));if (is_over_l == is_over_r) {if (!is_over_l) node[pos] = new_line;break;}int mid = (l + r) >> 1;bool is_over_mid =(new_line.eval(xs[mid]) >= node[pos].eval(xs[mid]));if (!is_over_l and is_over_r) {if (is_over_mid) {r = mid;pos = (pos << 1);} else {std::swap(new_line, node[pos]);l = mid;pos = (pos << 1) | 1;}} else {if (is_over_mid) {l = mid;pos = (pos << 1) | 1;} else {std::swap(new_line, node[pos]);r = mid;pos = (pos << 1);}}}}};int main() {int n, m;scanf("%d%d", &n, &m);vector<int> a(n), b(m);rep(i, n) scanf("%d", &a[i]);rep(i, m) scanf("%d", &b[i]);vector<lint> c(m);rep(i, m) scanf("%lld", &c[i]);vector<int> ab = a;ab.push_back(-1);for (auto x : b) ab.push_back(x);auto z = atcoder::z_algorithm(ab);z.erase(z.begin(), z.begin() + n + 1);vector<lint> xs(m + 10);iota(xs.begin(), xs.end(), 0);LiChaoTree<lint, LLONG_MAX> lct(xs);lct.add_segment(0, 0, 0, 1);rep(x, m) {auto val = lct.get_min(x);if (val == LLONG_MAX) continue;if (z[x] >= 1) {lct.add_segment(c[x], val - c[x] * x, x + 1, x + z[x] + 1);}}auto ans = lct.get_min(m);printf("%lld\n", ans == LLONG_MAX ? -1 : ans);}