結果
問題 | No.2332 Make a Sequence |
ユーザー | ponjuice |
提出日時 | 2023-05-28 15:52:47 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 222 ms / 2,000 ms |
コード長 | 9,763 bytes |
コンパイル時間 | 6,637 ms |
コンパイル使用メモリ | 317,404 KB |
実行使用メモリ | 39,376 KB |
最終ジャッジ日時 | 2023-08-27 13:12:23 |
合計ジャッジ時間 | 21,419 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 158 ms
32,628 KB |
testcase_08 | AC | 28 ms
7,276 KB |
testcase_09 | AC | 118 ms
24,312 KB |
testcase_10 | AC | 146 ms
30,252 KB |
testcase_11 | AC | 96 ms
20,784 KB |
testcase_12 | AC | 193 ms
37,776 KB |
testcase_13 | AC | 193 ms
39,376 KB |
testcase_14 | AC | 193 ms
37,488 KB |
testcase_15 | AC | 192 ms
37,660 KB |
testcase_16 | AC | 192 ms
37,664 KB |
testcase_17 | AC | 192 ms
37,668 KB |
testcase_18 | AC | 193 ms
37,920 KB |
testcase_19 | AC | 194 ms
38,000 KB |
testcase_20 | AC | 192 ms
38,144 KB |
testcase_21 | AC | 191 ms
37,396 KB |
testcase_22 | AC | 191 ms
38,740 KB |
testcase_23 | AC | 192 ms
37,972 KB |
testcase_24 | AC | 192 ms
37,456 KB |
testcase_25 | AC | 191 ms
38,780 KB |
testcase_26 | AC | 193 ms
37,724 KB |
testcase_27 | AC | 192 ms
37,556 KB |
testcase_28 | AC | 192 ms
38,428 KB |
testcase_29 | AC | 192 ms
37,920 KB |
testcase_30 | AC | 191 ms
37,800 KB |
testcase_31 | AC | 193 ms
37,828 KB |
testcase_32 | AC | 194 ms
37,604 KB |
testcase_33 | AC | 195 ms
38,228 KB |
testcase_34 | AC | 193 ms
38,384 KB |
testcase_35 | AC | 194 ms
37,788 KB |
testcase_36 | AC | 195 ms
37,544 KB |
testcase_37 | AC | 193 ms
37,544 KB |
testcase_38 | AC | 192 ms
37,288 KB |
testcase_39 | AC | 192 ms
38,240 KB |
testcase_40 | AC | 193 ms
37,648 KB |
testcase_41 | AC | 192 ms
37,864 KB |
testcase_42 | AC | 191 ms
36,112 KB |
testcase_43 | AC | 192 ms
34,508 KB |
testcase_44 | AC | 192 ms
35,812 KB |
testcase_45 | AC | 194 ms
36,476 KB |
testcase_46 | AC | 194 ms
35,692 KB |
testcase_47 | AC | 193 ms
30,876 KB |
testcase_48 | AC | 193 ms
30,908 KB |
testcase_49 | AC | 194 ms
30,872 KB |
testcase_50 | AC | 193 ms
31,232 KB |
testcase_51 | AC | 194 ms
30,908 KB |
testcase_52 | AC | 191 ms
38,964 KB |
testcase_53 | AC | 192 ms
38,416 KB |
testcase_54 | AC | 191 ms
38,660 KB |
testcase_55 | AC | 193 ms
37,600 KB |
testcase_56 | AC | 191 ms
38,484 KB |
testcase_57 | AC | 192 ms
38,180 KB |
testcase_58 | AC | 191 ms
37,732 KB |
testcase_59 | AC | 191 ms
38,560 KB |
testcase_60 | AC | 193 ms
37,848 KB |
testcase_61 | AC | 191 ms
38,328 KB |
testcase_62 | AC | 222 ms
34,468 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; //高速化 struct ponjuice{ponjuice(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);}}PonJuice; //#define endl '\n' //インタラクティブ問題の時は消す //型 using ll = long long; using ld = long double; using mint = modint998244353;//1000000007; template<class T>using vc = vector<T>; template<class T>using vvc = vc<vc<T>>; template<class T>using vvvc = vvc<vc<T>>; using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>; using vl = vc<ll>; using vvl = vvc<ll>; using vvvl = vvvc<ll>; using pi = pair<int, int>; using pl = pair<ll, ll>; using ull = unsigned ll; template<class T>using priq = priority_queue<T>; template<class T>using priqg = priority_queue<T, vc<T>, greater<T>>; // for文 #define overload4(a, b, c, d, e, ...) e #define rep1(n) for(ll i = 0; i < n; i++) #define rep2(i, n) for(ll i = 0; i < n; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, step) for(ll i = a; i < b; i+= step) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define per1(n) for(ll i = n-1; i >= 0; i--) #define per2(i, n) for(ll i = n-1; i >= 0; i--) #define per3(i, a, b) for(ll i = b-1; i >= a; i--) #define per4(i, a, b, step) for(ll i = b-1; i >= a; i-= step) #define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__) #define fore1(a) for(auto&& i : a) #define fore2(i,a) for(auto&& i : a) #define fore3(x,y,a) for(auto&& [x, y] : a) #define fore4(x,y,z,a) for(auto&& [x, y, z] : a) #define fore(...) overload4(__VA_ARGS__, fore4, fore3, fore2, fore1)(__VA_ARGS__) //関数 #define mp make_pair #define mt make_tuple #define a first #define b second #define pb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define si(x) (ll)(x).size() template<class S, class T>inline bool chmax(S& a, T b){return a < b && ( a = b , true);} template<class S, class T>inline bool chmin(S& a, T b){return a > b && ( a = b , true);} template<class T>void uniq(vc<T>&a){sort(all(a));a.erase(unique(all(a)),a.end());} template<class T>vc<T> operator++(vc<T>&v,signed){auto res = v;fore(e,v)e++;return res;} template<class T>vc<T> operator--(vc<T>&v,signed){auto res = v;fore(e,v)e--;return res;} template<class T>vc<T> operator++(vc<T>&v){fore(e,v)e++;return v;} template<class T>vc<T> operator--(vc<T>&v){fore(e,v)e--;return v;} //入出力(operator) template<int T>istream&operator>>(istream&is,static_modint<T>&a){ll v;is>>v;a=v;return is;} istream&operator>>(istream&is,modint&a){ll v;cin>>v;a=v;return is;} template<class S,class T>istream&operator>>(istream&is,pair<S,T>&a){is>>a.a>>a.b;return is;} template<class T>istream&operator>>(istream&is,vc<T>&a){fore(e,a)is>>e;return is;} template<int T>ostream&operator<<(ostream&os,static_modint<T>a){return os<<a.val();} ostream&operator<<(ostream&os,modint a){return os<<a.val();} template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>&a){return os<<a.a<<" "<<a.b;} template<class T>ostream&operator<<(ostream&os,set<T>&a){fore(it,a){os<<it<<" ";}return os;} template<class T>ostream&operator<<(ostream&os,multiset<T>&a){fore(it,a){os<<it<<" ";}return os;} template<class S,class T>ostream&operator<<(ostream&os,map<S,T>&a){fore(x,y,a){os<<x<<" "<<y<<"\n";}return os;} template<class T>ostream&operator<<(ostream&os,unordered_set<T>&a){fore(it,a){os<<it<<" ";}return os;} template<class S,class T>ostream&operator<<(ostream&os,unordered_map<S,T>&a){fore(x,y,a){os<<x<<" "<<y<<"\n";}return os;} template<class T>ostream&operator<<(ostream&os,vc<T>&a){fore(e,a)os<<e<<" ";return os;} template<class T>ostream&operator<<(ostream&os,vvc<T>&a){fore(e,a)os<<e<<"\n";return os;} //入出力(関数) vi readvi(ll n){vi a(n);cin>>a;return a;} vl readvl(ll n){vl a(n);cin>>a;return a;} vvi readg(ll n,ll m,bool bidirected=true){vvi g(n);rep(i,m){ll a,b;cin>>a>>b;a--;b--;g[a].pb(b);if(bidirected)g[b].pb(a);}return g;} vvc<pi>readgc(ll n,ll m,bool bidirected=true){vvc<pi> g(n);rep(i,m){ll a,b,c;cin>>a>>b>>c;a--;b--;g[a].pb(b,c);if(bidirected)g[b].pb(a,c);}return g;} vvi readt(ll n,bool bidirected=true){return readg(n,n-1,bidirected);} vvc<pi> readtc(ll n,bool bidirected=true){return readgc(n,n-1,bidirected);} inline void yes(){cout << "Yes\n";} inline void no(){cout << "No\n";} inline void yesno(bool y = true){if(y)yes();else no();} inline void print(){cout<<endl;} template<class T>inline void print(T a){cout<<a<<endl;} template<class T,class... Ts>inline void print(T a,Ts ...b){cout<<a;(cout<<...<<(cout<<' ',b));cout<<endl;} //定数 constexpr ll mod = 998244353; constexpr ll minf=-(1<<29); constexpr ll MINF=-(1LL<<60); constexpr ll INF=(1LL<<60); constexpr ld EPS = 1e-8; const ld PI = acosl(-1); #define equals(a, b) (abs((a) - (b)) < EPS) const int dx[4] ={-1, 0, 1, 0}; const int dy[4] ={ 0, 1, 0,-1}; const int dx8[8] ={-1,-1,-1, 0, 1, 1, 1, 0}; const int dy8[8] ={-1, 0, 1, 1, 1, 0,-1,-1}; void solve(); int main() { int t = 1; // cin >>t; while(t--)solve(); } #include <algorithm> using ll = long long; using namespace std; const static ll inf = 1e18L; class LiChaoTree { struct Line { ll a, b; Line(ll a, ll b) : a(a), b(b) {} Line() : a(0), b(0) {} inline ll f(ll x) const { return a * x + b; } Line& operator+=(const Line &ln) { if (b >= inf || ln.b >= inf) { a = 0; b = inf; } else { a += ln.a; b += ln.b; } return *this; } bool operator==(const Line &ln) const { return a == ln.a && b == ln.b; } }; const Line line_inf = Line{0, inf}; const Line line_zero = Line{0, 0}; struct Node { Node *left, *right; Line line, lazy; Node(Line line) : left(nullptr), right(nullptr), line(line) {} }; Node *root; ll xl, xr; inline bool compare(Line &l0, Line &l1, ll x) const { return l0.f(x) <= l1.f(x); } inline void _push_line(Node *nd, ll l, ll r) { if (nd == nullptr || nd->line == line_inf) return; ll m = (l + r) / 2; nd->left = _add_line(nd->left, nd->line, l, m); nd->right = _add_line(nd->right, nd->line, m, r); nd->line = line_inf; } inline void _add_lazy(Node *nd, Line &line) { if (nd == nullptr) return; nd->line += line; nd->lazy += line; } inline void _push_lazy(Node *nd, ll l, ll r) { if (nd == nullptr || nd->lazy == line_zero) return; _add_lazy(nd->left, nd->lazy); _add_lazy(nd->right, nd->lazy); nd->lazy = line_zero; } Node* _add_line(Node *nd, Line line, ll l, ll r) { if (l == r) return nullptr; ll m = (l + r) / 2; if (nd == nullptr) return new Node(line); _push_lazy(nd, l, r); bool left = compare(line, nd->line, l); bool mid = compare(line, nd->line, m); bool right = compare(line, nd->line, r); if (mid) { swap(nd->line, line); } if(r-l > 1 && left != right) { if (left != mid) { nd->left = _add_line(nd->left, line, l, m); } else { nd->right = _add_line(nd->right, line, m, r); } } return nd; } Node* _add_val(ll a, ll b, Node *nd, Line &line, ll l, ll r) { if (r <= a || b <= l) { return nd; } if (a <= l && r <= b) { _add_lazy(nd, line); return nd; } _push_lazy(nd, l, r); _push_line(nd, l, r); if (nd == nullptr) { nd = new Node(line_inf); } ll m = (l + r) / 2; nd->left = _add_val(a, b, nd->left, line, l, m); nd->right = _add_val(a, b, nd->right, line, m, r); return nd; } Node* _add_segment_line(ll a, ll b, Node *nd, Line &line, ll l, ll r) { if (r <= a || b <= l) { return nd; } if (a <= l && r <= b) { return _add_line(nd, line, l, r); } _push_lazy(nd, l, r); if (nd == nullptr) { nd = new Node(line_inf); } ll m = (l + r) / 2; nd->left = _add_segment_line(a, b, nd->left, line, l, m); nd->right = _add_segment_line(a, b, nd->right, line, m, r); return nd; } ll _query_min(ll k, ll l, ll r) { Node *nd = root; ll s = inf; while (r - l > 0 && nd != nullptr) { ll m = (l + r) / 2; _push_lazy(nd, l, r); s = min(s, nd->line.f(k)); if (k < m) { r = m; nd = nd->left; } else { l = m; nd = nd->right; } } return s; } public: LiChaoTree(ll xl, ll xr) : xl(xl), xr(xr), root(nullptr) {} // a_i <- min(a_i, a*i + b) for i in [xl, xr) void add_line(ll a, ll b) { Line line = Line{a, b}; root = _add_line(root, line, xl, xr); } // a_i <- min(a_i, a*i + b) for i in [l, r) void add_segment_line(ll a, ll b, ll l, ll r) { Line line = Line{a, b}; root = _add_segment_line(l, r, root, line, xl, xr); } // a_i <- a_i + (a*i + b) for i in [l, r) void add_val(ll a, ll b, ll l, ll r) { Line line = Line{a, b}; root = _add_val(l, r, root, line, xl, xr); } // a_i <- +∞ for i in [l, r) void reset_val(ll l, ll r) { Line line = line_inf; root = _add_val(l, r, root, line, xl, xr); } // get a_i ll query_min(ll x) { return _query_min(x, xl, xr); } }; void solve(){ int n,m; cin>>n >> m; vl a = readvl(n); vl b = readvl(m); vl c = readvl(m); vl z = a; z.emplace_back(-1); rep(i,m){ z.emplace_back(b[i]); } vi za = z_algorithm(z); LiChaoTree tree(0, m+1); tree.add_segment_line(0,0,0,1); rep(i,m){ ll cost = tree.query_min(i); tree.add_segment_line(c[i],(cost-c[i]*i),i,i+za[n+1+i]+1); } print(tree.query_min(m)==inf?-1:tree.query_min(m)); }