結果

問題 No.705 ゴミ拾い Hard
ユーザー noiminoimi
提出日時 2024-08-16 18:41:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 270 ms / 1,500 ms
コード長 4,798 bytes
コンパイル時間 3,178 ms
コンパイル使用メモリ 225,184 KB
実行使用メモリ 13,808 KB
最終ジャッジ日時 2024-08-16 18:41:50
合計ジャッジ時間 10,763 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 263 ms
13,696 KB
testcase_25 AC 258 ms
13,568 KB
testcase_26 AC 265 ms
13,760 KB
testcase_27 AC 266 ms
13,808 KB
testcase_28 AC 265 ms
13,568 KB
testcase_29 AC 260 ms
13,696 KB
testcase_30 AC 258 ms
13,696 KB
testcase_31 AC 236 ms
13,568 KB
testcase_32 AC 248 ms
13,568 KB
testcase_33 AC 146 ms
13,568 KB
testcase_34 AC 144 ms
13,804 KB
testcase_35 AC 181 ms
13,568 KB
testcase_36 AC 222 ms
13,568 KB
testcase_37 AC 181 ms
13,696 KB
testcase_38 AC 220 ms
13,568 KB
testcase_39 AC 234 ms
13,696 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 270 ms
13,568 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:20:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   20 | bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
      |            ^~~~
main.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   20 | bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
      |                     ^~~~
main.cpp:21:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   21 | bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
      |            ^~~~
main.cpp:21:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   21 | bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
      |                     ^~~~

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov3(a, b, c, name, ...) name
#define rep0(n) for(ll aaaaa = 0; aaaaa < (n); aaaaa++)
#define rep1(i, n) for(ll i = 0; i < (n); i++)
#define rep2(i, a, b) for(ll i = (a); i < (b); i++)
#define rep(...) ov3(__VA_ARGS__, rep2, rep1, rep0)(__VA_ARGS__)
#define fore(e, v) for(auto &&e : v)
#define all(v) begin(v), end(v)
#define si(a) (int)(size(a))
bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
const int inf = 11e8;
const ll infl = 2e18;

#define i128 __int128_t

template <bool isMin = true> struct CHT {
#define x first
#define y second
    CHT() = default;
    deque<pll> v;
    bool empty() { return v.empty(); }
    void clear() { return v.clear(); }
    inline int sgn(ll x) { return !x ? 0 : (x < 0 ? -1 : 1); }
    using D = long double;
    inline bool check(const pll &a, const pll &b, const pll &c) {
        if(b.y == a.y or c.y == b.y) return sgn(b.x - a.x) * sgn(c.y - b.y) >= sgn(c.x - b.x) * sgn(b.y - a.y);
        return D(b.x - a.x) * sgn(c.y - b.y) / D(abs(b.y - a.y)) >= D(c.x - b.x) * sgn(b.y - a.y) / D(abs(c.y - b.y));
    }
    void add(ll a, ll b) {
        if(!isMin) a *= -1, b *= -1;
        pll line(a, b);
        if(empty())
            v.emplace_front(line);
        else {
            if(ll c = v[0].x; c <= a) {
                if(c == a) {
                    if(v[0].y <= b) return;
                    v.pop_front();
                }
                while(si(v) >= 2 and check(line, v[0], v[1])) v.pop_front();
                v.emplace_front(line);
            } else {
                assert(a <= v.back().x);
                if(v.back().x == a) {
                    if(v.back().y <= b) return;
                    v.pop_back();
                }
                while(si(v) >= 2 and check(v[si(v) - 2], v.back(), line)) v.pop_back();
                v.emplace_back(line);
            }
        }
    }
    ll get_y(const pll &a, const ll &x) { return a.x * x + a.y; }
    ll query(ll x) {
        assert(!empty());
        int l = -1, r = si(v) - 1;
        while(l + 1 < r) {
            int m = (l + r) >> 1;
            if(get_y(v[m], x) >= get_y(v[m + 1], x))
                l = m;
            else
                r = m;
        }
        return get_y(v[r], x) * (isMin ? 1 : -1);
    }
    ll query_monotone_inc(ll x) {
        assert(!empty());
        while(si(v) >= 2 and get_y(v[0], x) >= get_y(v[1], x)) v.pop_front();
        return get_y(v[0], x) * (isMin ? 1 : -1);
    }
    ll query_monotone_dec(ll x) {
        assert(!empty());
        while(si(v) >= 2 and get_y(v.back(), x) >= get_y(v.end()[-2], x)) v.pop_back();
        return get_y(v.back(), x) * (isMin ? 1 : -1);
    }
#undef x
#undef y
};

// A[N + 1][N + 1]: Monge が i > j のみ存在しているとき、i (= 0, ..., N)行目の最小値を返す
// f(i, j, v) で、j 行目の最小値が求まっている v を用いて、A[i][j] にアクセス
template <typename T, typename F> vector<T> monge_rowmin(int n, const F &f) {
    vector<T> mi(n + 1, numeric_limits<T>::max());
    mi[0] = 0;
    vector<int> amin(n + 1);
    auto check = [&](int i, int j) {
        if(chmin(mi[i], f(i, j, mi))) { amin[i] = j; }
    };
    check(n, 0);
    auto solve = [&](auto &&self, int l, int r) {
        if(r - l == 1) return;
        int mid = l + r >> 1;
        rep(k, amin[l], amin[r] + 1) check(mid, k);
        self(self, l, mid);
        rep(k, l + 1, mid + 1) check(r, k);
        self(self, mid, r);
    };
    solve(solve, 0, n);
    return mi;
}

// monotone 行列の各行について、最小値を取る場所とその値を返す
template <typename T, typename F> vector<pair<int, T>> monotone_minima(int h, int w, const F &f) {
    vector<pair<int, T>> dp(h, pair(-1, T()));
    auto rec = [&](auto &&rec, int u, int d, int l, int r) {
        if(u > d) return;
        int mid = u + d >> 1;
        auto &[idx, mi] = dp[mid];
        idx = l, mi = f(mid, l);
        rep(i, l + 1, r + 1) if(chmin(mi, f(mid, i))) idx = i;
        rec(rec, u, mid - 1, l, idx);
        rec(rec, mid + 1, d, idx, r);
    };
    rec(rec, 0, h - 1, 0, w - 1);
    return dp;
}

int main() {
    int n;
    cin >> n;
    vl a(n), x(n), y(n);
    fore(e, a) cin >> e;
    fore(e, x) cin >> e;
    fore(e, y) cin >> e;

    auto p3 = [&](ll x) { return x * x * x; };

    auto cost = [&](int i, int j) { return p3(abs(a[j - 1] - x[i])) + p3(y[i]); };

    auto f = [&](int j, int i, vl &v) { return v[i] + cost(i, j); };

    cout << monge_rowmin<ll>(n, f)[n] << endl;
}
0