結果

問題 No.705 ゴミ拾い Hard
コンテスト
ユーザー askr58
提出日時 2026-11-16 07:28:33
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 75 ms / 1,500 ms
+ 814µs
コード長 8,884 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,413 ms
コンパイル使用メモリ 345,416 KB
実行使用メモリ 13,952 KB
最終ジャッジ日時 2026-11-16 07:28:45
合計ジャッジ時間 11,796 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

// SPDX-License-Identifier: CC0-1.0
//
// [English]
// To the extent possible under law, the author(s) have dedicated all copyright
// and related and neighboring rights to this software to the public domain
// worldwide. This software is distributed without any warranty.
// See <https://creativecommons.org/publicdomain/zero/1.0/> for details.
//
// [日本語]
// 法律上可能な範囲で、著作者はこのソフトウェアに関する著作権および
// 著作隣接権を含むすべての関連する権利を、全世界でパブリックドメインに
// 提供しています。本ソフトウェアは一切の保証なく配布されます。
// 自由にコピー・改変・再配布・商用利用できます(クレジット表記は不要です)。
// 詳細は <https://creativecommons.org/publicdomain/zero/1.0/deed.ja> を参照してください。
// ※ 英語の文面および CC0 1.0 の正式な条文(英語)が優先されます。

#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=std::int64_t;

#include <atcoder/all>
using mint=atcoder::modint998244353;

ostream& operator<<(ostream& os,const mint& x){
	os<<x.val();
	return os;
}
istream& operator>>(istream& is,mint& x){
	int t;
	is>>t;
	x=t;
	return is;
}

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p);
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p);
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr);
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr);
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec);
template <typename T>
istream& operator>>(istream& is,vector<T>& vec);

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p){
	os<<p.first<<" "<<p.second;
	return os;
}
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p){
	is>>p.first>>p.second;
	return is;
}

template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr){
	for(int i=0;i<n;i++)os<<arr[i]<<(i+1==n?"":" ");
	return os;
}
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr){
	for(int i=0;i<n;i++)is>>arr[i];
	return is;
}
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
	for(int i=0;i<(int)vec.size();i++)os<<vec[i]<<(i+1==(int)vec.size()?"":" ");
	return os;
}
template <typename T>
istream& operator>>(istream& is,vector<T>& vec){
	for(int i=0;i<(int)vec.size();i++)is>>vec[i];
	return is;
}

template<class... Vecs>
void input_vec(Vecs&... vs) {
    const auto n = get<0>(tie(vs...)).size();

    for (size_t i = 0; i < n; ++i)
        ((cin >> vs[i]), ...);
}

template <class... Vecs>
void output_vec(const Vecs&... vs) {
    const auto n = get<0>(tie(vs...)).size();

    for (size_t i = 0; i < n; ++i) {
        bool first = true;
        (((cout << (exchange(first, false) ? "" : " ") << vs[i])), ...);
        cout << endl;
    }
}

template <typename T>
vector<T> make_unique(vector<T> vec){
	ranges::sort(vec);
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	return vec;
}

vector<int> Iota(int n,int s=0){
	vector<int> res(n);
	iota(res.begin(),res.end(),s);
	return res;
}

vector<ll> Iotall(int n,ll s=0){
	vector<ll> res(n);
	iota(res.begin(),res.end(),s);
	return res;
}
void YESNO(bool f){
	if(f)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>; 
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vvvi=vector<vector<vector<int>>>;


namespace larsch_detail {

template <class T>
class RowMinima {
    using Evaluate = std::function<T(int, int)>;

    int n_;
    Evaluate evaluate_;

    int next_row_ = 0;
    int bound_ = 0;

    std::vector<int> columns_;
    std::unique_ptr<RowMinima<T>> child_;

public:
    // evaluate(row, col) の有効領域は 0 <= col <= row < n。
    // 将来の行を評価してもよいが、列はオンラインに利用する。
    RowMinima(int n, Evaluate evaluate)
        : n_(n), evaluate_(std::move(evaluate)) {
        const int m = n_ / 2;

        if (m > 0) {
            columns_.reserve(static_cast<std::size_t>(m));

            child_ = std::make_unique<RowMinima<T>>(
                m,
                [this](int row, int col) -> T {
                    return evaluate_(2 * row + 1, columns_[col]);
                }
            );
        }
    }

    // 子の評価関数が this を参照するため、移動も禁止する。
    RowMinima(const RowMinima&) = delete;
    RowMinima& operator=(const RowMinima&) = delete;
    RowMinima(RowMinima&&) = delete;
    RowMinima& operator=(RowMinima&&) = delete;

    // 行 0, 1, ..., n - 1 の順に、最小値を取る列を返す。
    int next_argmin() {
        const int row = next_row_++;

        if ((row & 1) != 0) {
            // 直前の先読みで扱っていない新しい列だけを比較する。
            if (evaluate_(row, row) < evaluate_(row, bound_)) {
                return row;
            }
            return bound_;
        }

        const int begin = bound_;
        int end = n_ - 1;

        if (row + 1 < n_) {
            const int reduced_row = row / 2;
            const int capacity = n_ / 2;

            if (reduced_row == 0) {
                columns_.push_back(0);
            } else {
                // 列削減。先頭 reduced_row 列は再帰側で使用済みなので
                // 変更せず、それ以降の候補だけを削除する。
                for (int col = row - 1; col <= row; ++col) {
                    while (
                        static_cast<int>(columns_.size()) > reduced_row
                    ) {
                        const int rank =
                            static_cast<int>(columns_.size()) - 1;

                        if (
                            evaluate_(2 * rank + 1, col)
                            < evaluate_(2 * rank + 1, columns_.back())
                        ) {
                            columns_.pop_back();
                        } else {
                            break;
                        }
                    }

                    if (
                        static_cast<int>(columns_.size()) < capacity
                    ) {
                        columns_.push_back(col);
                    }
                }
            }

            // 次の奇数行を、現時点で利用可能な列だけで先読みする。
            end = columns_[child_->next_argmin()];
        }

        bound_ = end;

        // 単調性により、この区間だけ調べればよい。
        int best = begin;

        for (int col = begin + 1; col <= end; ++col) {
            if (evaluate_(row, col) < evaluate_(row, best)) {
                best = col;
            }
        }

        return best;
    }
};

}  // namespace larsch_detail

// A(i, k, dp_k) = dp[k] + w(k, i)
//
// 前提:
//   - A は最小化の向きの Monge 性を満たす。
//   - 同じ引数に対する A の返値は変化しない。
//   - 評価と比較でオーバーフローや NaN が発生しない。
//
// 戻り値:
//   dp[0] = 0
//   dp[i] = min_{0 <= k < i} A(i, k, dp[k])  (1 <= i <= N)
//
// 計算量:
//   A の評価回数 O(N)、追加領域 O(N)。
template <class T = std::int64_t, typename Matrix>
std::vector<T> larsch(int N, Matrix A) {
    if (N < 0) {
        throw std::invalid_argument("larsch: N must be nonnegative");
    }

    std::vector<T> dp(
        static_cast<std::size_t>(N) + 1,
        T{0}
    );

    if (N == 0) {
        return dp;
    }

    // 内部の行 row を、画像の行 i = row + 1 に対応させる。
    auto evaluate = [&](int row, int col) -> T {
        return std::invoke(
            A,
            row + 1,
            col,
            std::as_const(dp[col])
        );
    };

    larsch_detail::RowMinima<T> solver(N, evaluate);

    for (int row = 0; row < N; ++row) {
        const int col = solver.next_argmin();
        dp[row + 1] = evaluate(row, col);
    }

    return dp;
}

// Aは(i,j,dp_j)を受け取って値を返します
// 普通のk辺最短路ならA(i,j,dp_j)=dp_j+w(j,i)とすればok

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	vl a(n),x(n),y(n);
	cin>>a>>x>>y;
	auto w=[&](int i,int j){
		j--;
		return abs((a[j]-x[i])*(a[j]-x[i])*(a[j]-x[i]))+abs(y[i]*y[i]*y[i]);
	};
	auto ans=larsch(n,[&](int i,int j,ll dp_j)->ll{
		return dp_j+w(j,i);
	});
	cout<<ans[n]<<endl;
}

	
0