結果
問題 | No.704 ゴミ拾い Medium |
ユーザー |
![]() |
提出日時 | 2018-06-15 22:54:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 1,500 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 1,818 ms |
コンパイル使用メモリ | 177,976 KB |
実行使用メモリ | 14,592 KB |
最終ジャッジ日時 | 2024-06-30 15:14:02 |
合計ジャッジ時間 | 6,702 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
#include "bits/stdc++.h" using namespace std; template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; } const long long INFL = 0x3f3f3f3f3f3f3f3fLL;; struct DynamicRMQ { typedef long long Val; int n; vector<Val> d; void init(int nmin) { for (n = 1; n < nmin; n *= 2); d.assign(n * 2, INFL); } void update(int i, Val x) { d[n + i] = x; for (int k = (n + i) / 2; k > 0; k >>= 1) d[k] = min(d[k * 2], d[k * 2 + 1]); } Val get(int i) const { return d[n + i]; } //[l, r) Val query(int l, int r) const { Val m = INFL; for (; l && l + (l&-l) <= r; l += l & -l) m = min(m, d[(n + l) / (l&-l)]); for (; l < r; r -= r & -r) m = min(m, d[(n + r) / (r&-r) - 1]); return m; } }; int main() { int N; while (~scanf("%d", &N)) { vector<int> as(N); for (int i = 0; i < N; ++ i) scanf("%d", &as[i]); vector<int> xs(N); for (int i = 0; i < N; ++ i) scanf("%d", &xs[i]); vector<int> ys(N); for (int i = 0; i < N; ++ i) scanf("%d", &ys[i]); auto values = xs; sort(values.begin(), values.end()); values.erase(unique(values.begin(), values.end()), values.end()); DynamicRMQ rmqL, rmqR; rmqL.init((int)values.size()); rmqR.init((int)values.size()); vector<long long> dp(N + 1, INFL); dp[0] = 0; for (int i = 0; i < N; ++ i) { { auto xi = (int)(lower_bound(values.begin(), values.end(), xs[i]) - values.begin()); rmqL.update(xi, min(dp[i] + ys[i] - xs[i], rmqL.get(xi))); rmqR.update(xi, min(dp[i] + ys[i] + xs[i], rmqR.get(xi))); } long long t = INFL; // for (int j = 0; j <= i; ++ j) // amin(t, dp[j] + abs(as[i] - xs[j]) + ys[j]); { auto xi = (int)(lower_bound(values.begin(), values.end(), as[i]) - values.begin()); amin(t, rmqL.query(0, xi) + as[i]); amin(t, rmqR.query(xi, (int)values.size()) - as[i]); } dp[i + 1] = t; } long long ans = dp[N]; printf("%lld\n", ans); } }