結果
問題 |
No.705 ゴミ拾い Hard
|
ユーザー |
![]() |
提出日時 | 2024-03-20 23:14:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 440 ms / 1,500 ms |
コード長 | 2,863 bytes |
コンパイル時間 | 2,180 ms |
コンパイル使用メモリ | 202,516 KB |
最終ジャッジ日時 | 2025-02-20 10:04:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i32 = int; using i64 = long long; using i128 = __int128_t; using u32 = unsigned; using u64 = unsigned long long; using u128 = __uint128_t; using pi = pair<i32, i32>; template <typename T> using V = vector<T>; template <typename T> using VV = vector<V<T>>; template <typename T> using VVV = vector<VV<T>>; template <typename T> using PQR = priority_queue<T, V<T>, greater<>>; #define OVERRIDE4(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i) #define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i) #define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i) #define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__) #define ALL(x) begin(x), end(x) #define LEN(x) (i32) x.size() 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> i32 lob(const V<T> &arr, T x) { return (i32)(lower_bound(ALL(arr), x) - arr.begin()); } template <typename T> i32 upb(const V<T> &arr, T x) { return (i32)(upper_bound(ALL(arr), x) - arr.begin()); } // ----------------------------------- constexpr i64 INF64 = 3003003003003003003; int main() { i32 n; cin >> n; V<i64> a(n), x(n), y(n); REP(i, n) { cin >> a[i]; } REP(i, n) { cin >> x[i]; } REP(i, n) { cin >> y[i]; } auto cost = [&](i32 l, i32 r) -> i64 { i64 dx = abs(a[r - 1] - x[l]); i64 dy = y[l]; return dx * dx * dx + dy * dy * dy; }; // cost(0, i) < INF64 なので、dp[i] < INF64 V<i64> dp(n + 1, INF64); dp[0] = 0; // i < j auto cross = [&](i32 i, i32 j) -> i32 { i32 ok = j, ng = n + 1; while (ng - ok > 1) { i32 mid = (ok + ng) / 2; if (dp[i] + cost(i, mid) < dp[j] + cost(j, mid)) { ok = mid; } else { ng = mid; } } return ng; }; deque<pair<i32, i32>> deq; deq.emplace_back(0, n + 1); REP(i, 1, n + 1) { while (deq.front().second <= i) { deq.pop_front(); } dp[i] = dp[deq.front().first] + cost(deq.front().first, i); while (LEN(deq) >= 2) { i32 tmp = cross(deq.back().first, i); if (deq[LEN(deq) - 2].second >= tmp) { deq.pop_back(); } else { break; } } deq.back().second = cross(deq.back().first, i); deq.emplace_back(i, n + 1); } cout << dp[n] << '\n'; }