結果
| 問題 | No.705 ゴミ拾い Hard |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-16 07:28:33 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 75 ms / 1,500 ms |
| + 814µs | |
| コード長 | 8,884 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
// 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;
}