// 基本テンプレート #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} typedef pair pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; // Abstract Segment Tree (抽象・汎化セグメント木) // Verified: AOJ DSL_2_A: Range Minimum Query (int型のみ) const int SIZE = 1 << 19; template struct segtree { // ノード、単位元 T node[2*SIZE], I; // オペレーション (update, query の 2 つが必要?) T (*upd_f)(T, T), (*qry_f)(T, T); // 演算子と単位元をセットし、全ての node を単位元で初期化 segtree(T (*op1)(T, T), T (*op2)(T, T), T X) { upd_f = op1; qry_f = op2; I = X; fill(node, node+2*SIZE, I); } // 配列 vec の値で初期化 void init(vector vec) { int N = (int)vec.size(); for(int i=0; i=0; i--) { node[i] = qry_f(node[2*i+1], node[2*i+2]); } } // 場所 idx に値 val を反映 (upd_f を用いて update) void update(int idx, T val) { idx += SIZE - 1; node[idx] = upd_f(node[idx], val); while(idx > 0) { // 登るときは qry_f を使うことに注意!!! idx = (idx - 1) / 2; node[idx] = qry_f(node[2*idx+1], node[2*idx+2]); } } // 半開区間 [a, b) に対してクエリを投げる // (qry_f を用いて処理) T query(int a, int b, int l=0, int r=SIZE, int k=0) { if(b <= l || r <= a) return I; if(a <= l && r <= b) return node[k]; int mid = (l + r) / 2; T vl = query(a, b, l, mid, 2*k+1); T vr = query(a, b, mid, r, 2*k+2); return qry_f(vl, vr); } }; // [[つかいかた]] // update 用と query 用の関数と単位元 (関数を噛ませても結果が変わらないもの) を用意して宣言する // 下の例だと、update 用の関数が upd で、query 用の関数が fnd で、単位元が INT_MAX int upd(int a, int b) {return b;} int fnd(int a, int b) {return min(a, b);} segtree seg_minus(upd, fnd, 1LL << 60); segtree seg_plus(upd, fnd, 1LL << 60); signed main() { int N; cin >> N; vector A(N+1), X(N+1), Y(N+1); for(int i=0; i> A[i+1]; for(int i=0; i> X[i+1]; for(int i=0; i> Y[i+1]; vector dp(N+1, INF); dp[0] = 0; int it = 1; for(int i=1; i<=N; i++) { dp[i] = dp[i-1] + abs(A[i] - X[i]) + Y[i]; chmin(dp[i], seg_minus.query(0, i) + A[i]); chmin(dp[i], seg_plus.query(0, i) - A[i]); seg_plus.update(i, dp[i-1] + Y[i] + X[i]); while(it <= i && X[it] < A[i+1]) { int val = dp[it-1] + Y[it] - X[it]; seg_plus.update(it, INF); seg_minus.update(it, val); it++; } } cout << dp[N] << endl; return 0; }