結果
問題 |
No.705 ゴミ拾い Hard
|
ユーザー |
![]() |
提出日時 | 2019-12-25 07:00:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 292 ms / 1,500 ms |
コード長 | 1,171 bytes |
コンパイル時間 | 1,765 ms |
コンパイル使用メモリ | 166,072 KB |
実行使用メモリ | 9,256 KB |
最終ジャッジ日時 | 2024-09-24 08:04:13 |
合計ジャッジ時間 | 8,768 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
main.cpp: In function ‘int ri()’: main.cpp:5:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 5 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp: In function ‘void monotone_minima(int, int, int, int)’: main.cpp:28:36: warning: ‘ind’ may be used uninitialized in this function [-Wmaybe-uninitialized] 28 | if (y1 < m) monotone_minima(x1, ind + 1, y1, m); | ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } std::vector<int> a, x, y; std::vector<int64_t> dp; int64_t cost(int i, int j) { int64_t x_dist = std::abs(a[j] - x[i]); int64_t y_dist = y[i]; return x_dist * x_dist * x_dist + y_dist * y_dist * y_dist; } void monotone_minima(int x1, int x2, int y1, int y2) { int m = y1 + (y2 - y1) / 2; assert(x1 < m); int64_t min = 1000000000000000000; int ind; for (int i = x1; i < x2 && i <= m; i++) { int64_t c = (i ? dp[i - 1] : 0) + cost(i, m); if (min > c) min = c, ind = i; } dp[m] = std::min(dp[m], min); if (y1 < m) monotone_minima(x1, ind + 1, y1, m); if (m + 1 < y2) monotone_minima(ind, x2, m + 1, y2); } void solve(int l, int r) { if (r - l == 1) { dp[l] = std::min(dp[l], (l ? dp[l - 1] : 0) + cost(l, l)); } else { int m = l + (r - l) / 2; solve(l, m); monotone_minima(l, m, m, r); solve(m, r); } } int main() { int n = ri(); a.resize(n); x.resize(n); y.resize(n); for (auto &i : a) i = ri(); for (auto &i : x) i = ri(); for (auto &i : y) i = ri(); dp.resize(n, 1000000000000000000); solve(0, n); std::cout << dp[n - 1] << std::endl; return 0; }