結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2024-07-04 15:31:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 91 ms / 1,500 ms |
コード長 | 3,053 bytes |
コンパイル時間 | 3,247 ms |
コンパイル使用メモリ | 252,924 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-07-04 15:31:53 |
合計ジャッジ時間 | 7,884 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<T>>; #define rep(i, l, r) for (ll i = (l); i < (r); i++) #define rrep(i, r, l) for (ll i = (r); i-- > (l);) #define all(x) begin(x), end(x) template <class T> bool chmin(T& lhs, T rhs) { return lhs > rhs ? (lhs = rhs, true) : false; } template <class T> bool chmax(T& lhs, T rhs) { return lhs < rhs ? (lhs = rhs, true) : false; } struct IOIO { IOIO() { cin.tie(0)->sync_with_stdio(0); } } ioio; template <class S, class T> ostream& operator<<(ostream& os, const pair<S, T>& p) { os << '(' << p.first << ", " << p.second << ')'; return os; } template <class T> ostream& operator<<(ostream& os, const vector<T>& vs) { os << '{'; rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", "); os << '}'; return os; } template <class T> ostream& operator<<(ostream& os, const set<T>& vs) { os << '{'; for (auto it = vs.begin(); it != vs.end(); it++) { if (it != vs.begin()) { os << ", "; } os << *it; } os << '}'; return os; } template <class T, class U> ostream& operator<<(ostream& os, const map<T, U>& vs) { os << '{'; for (auto it = vs.begin(); it != vs.end(); it++) { if (it != vs.begin()) { os << ", "; } os << *it; } os << '}'; return os; } #ifdef DEBUG void dump_func() { cerr << endl; } template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { cerr << head; if (sizeof...(Tail) > 0) { cerr << ", "; } dump_func(std::move(tail)...); } #define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__) #else #define dump(...) static_cast<int>(0) #endif int main() { int n; cin >> n; vector<ll> a(n), x(n), y(n); rep(i, 0, n) cin >> a[i]; rep(i, 0, n) cin >> x[i]; rep(i, 0, n) cin >> y[i]; using line = pair<ll, ll>; deque<line> deq; vector<ll> dp(n + 1); auto need = [](line a, line b, line c) { return (a.second - b.second) * (c.first - a.first) <= (a.second - c.second) * (b.first - a.first); }; auto eval = [](line l, ll x) { return l.first * x + l.second; }; rep(i, 0, n) { line l = {-2 * x[i], dp[i] + x[i] * x[i] + y[i] * y[i]}; if (!deq.empty() && deq.back().first == l.first) { auto l2 = deq.back(); deq.pop_back(); if (l2.second < l.second) { l = l2; } } while (deq.size() >= 2) { if (need(deq[deq.size() - 2], deq[deq.size() - 1], l)) { break; } else { deq.pop_back(); } } deq.push_back(l); while (deq.size() >= 2 && eval(deq[0], a[i]) >= eval(deq[1], a[i])) deq.pop_front(); dp[i + 1] = eval(deq.front(), a[i]) + a[i] * a[i]; } cout << dp.back() << '\n'; }