結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2021-04-06 23:52:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 1,500 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 852 ms |
コンパイル使用メモリ | 79,816 KB |
最終ジャッジ日時 | 2025-01-20 12:39:14 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <cassert> #include <cstddef> #include <deque> #include <iostream> #include <vector> __attribute__((constructor)) void fast_io() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } template <class T> class lines { public: void append(T a, T b) { if (lines.empty()) { lines.emplace_back(a, b); return; } auto [a1, b1] = lines.back(); while (lines.size() > 1) { auto [a0, b0] = lines[lines.size() - 2]; if ((a1 - a) * (b1 - b0) < (a0 - a1) * (b - b1)) break; lines.pop_back(); a1 = a0; b1 = b0; } lines.emplace_back(a, b); } T min_at(T x) { assert(!lines.empty()); auto [a0, b0] = lines[0]; T y0 = a0 * x + b0; while (lines.size() > 1) { auto [a1, b1] = lines[1]; T y1 = a1 * x + b1; if (y0 < y1) break; lines.pop_front(); a0 = a1; b0 = b1; y0 = y1; } return y0; } private: std::deque<std::pair<T, T>> lines; }; int main() { size_t n; std::cin >> n; std::vector<long long> a(n), x(n), y(n); for (auto& ai : a) std::cin >> ai; for (auto& xi : x) std::cin >> xi; for (auto& yi : y) std::cin >> yi; lines<long long> cht; long long dp = 0; for (size_t i = 0; i < n; ++i) { cht.append(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp); dp = cht.min_at(a[i]) + a[i] * a[i]; } std::cout << dp << '\n'; }