結果

問題 No.703 ゴミ拾い Easy
ユーザー nono00nono00
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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';
}
0