結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー askr58
提出日時 2026-11-16 06:31:37
言語 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  
実行時間 330 ms / 2,000 ms
+ 67µs
コード長 8,349 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,251 ms
コンパイル使用メモリ 349,508 KB
実行使用メモリ 144,896 KB
最終ジャッジ日時 2026-11-16 06:31:48
合計ジャッジ時間 10,743 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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=long long;

#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>>>;

// generated by ChatGPT outside of contest time.
// 各行の最小値を返す。行・列は 0-indexed。
//
// 前提:
//   任意の部分行列について、各行の「最左の最小値」の列番号が
//   上の行から下の行へ非減少であること(全単調性)。
//   f(r, c) の返す値は呼び出し間で変化しないこと。
//
// 計算量:
//   f の評価回数 O(H + W)
//   追加領域 O(H + W)
//
//   ワンポイントアドバイス:
//   下三角の場合、無効値の部分(i<j)はINF
//   上三角の場合、無効値の部分(i>j)はINF-j
//   とするとうまくらしいよv
template <class T = std::int64_t>
std::vector<T> smawk(
    int H,
    int W,
    std::function<T(int, int)> f
) {
    if (H < 0 || W < 0) {
        throw std::invalid_argument("smawk: negative matrix size");
    }
    if (H == 0) {
        return {};
    }
    if (W == 0) {
        throw std::invalid_argument("smawk: no columns");
    }

    std::vector<int> rows(H);
    std::vector<int> cols(W);
    std::iota(rows.begin(), rows.end(), 0);
    std::iota(cols.begin(), cols.end(), 0);

    // 最小値を取る最左の列番号を内部で求める。
    std::vector<int> argmin(H);

    auto solve = [&](
        auto&& self,
        const std::vector<int>& rs,
        const std::vector<int>& cs
    ) -> void {
        if (rs.empty()) {
            return;
        }

        const std::size_t n = rs.size();

        // 候補列を、行数以下になるまで削減する。
        std::vector<int> reduced;
        reduced.reserve(std::min(n, cs.size()));

        for (int c : cs) {
            while (!reduced.empty()) {
                const int r = rs[reduced.size() - 1];

                // 同値なら左側の列を残す。
                if (!(f(r, c) < f(r, reduced.back()))) {
                    break;
                }
                reduced.pop_back();
            }

            if (reduced.size() < n) {
                reduced.push_back(c);
            }
        }

        // 現在の行リストにおける奇数番目の行を再帰的に解く。
        std::vector<int> odd_rows;
        odd_rows.reserve(n / 2);

        for (std::size_t i = 1; i < n; i += 2) {
            odd_rows.push_back(rs[i]);
        }

        self(self, odd_rows, reduced);

        // 偶数番目の行を、隣接する奇数番目の行の解の間で探索する。
        std::size_t left = 0;

        for (std::size_t i = 0; i < n; i += 2) {
            std::size_t right;

            if (i + 1 < n) {
                right = left;
                while (reduced[right] != argmin[rs[i + 1]]) {
                    ++right;
                }
            } else {
                right = reduced.size() - 1;
            }

            const int r = rs[i];
            int best_col = reduced[left];
            T best_value = f(r, best_col);

            for (std::size_t j = left + 1; j <= right; ++j) {
                const int c = reduced[j];
                T value = f(r, c);

                if (value < best_value) {
                    best_value = std::move(value);
                    best_col = c;
                }
            }

            argmin[r] = best_col;
            left = right;
        }
    };

    solve(solve, rows, cols);

    std::vector<T> result;
    result.reserve(H);

    for (int r = 0; r < H; ++r) {
        result.push_back(f(r, argmin[r]));
    }

    return result;
}


// 頂点0,1,\cdots,n
// k=1,\cdots,nについてk辺最短路長を返す(0番目はダミー値が入る)
template <typename T=int64_t,T inf=(1ll<<61),typename Cost>
std::vector<T> enumerate_monge_shortest_path(int n,Cost cost){
	std::vector<std::vector<T>> dp(n+1,std::vector<T>(n+1));
	for(int i=1;i<=n;i++)dp[1][i]=cost(0,i);
	for(int k=2;k<=n;k++){
		auto f=[&](int i,int j)->T{
			if(i<j)return inf;
			return dp[k-1][j+k-1]+cost(j+k-1,i+k);
		};
		auto res=smawk<T>(n+1-k,n+1-k,f);
		for(int i=0;i<n+1-k;i++)dp[k][i+k]=res[i];
	}
	std::vector<T> ans(n+1);
	for(int i=1;i<=n;i++)ans[i]=dp[i][n];
	return ans;
}

	

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	vl a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	vl s(n+2);
	for(int i=0;i<=n;i++)s[i+1]=s[i]+a[i];
	vvl dp(n+2,vl(n+2));
	auto cost=[&](int i,int j)->ll{
		return (s[j]-s[i+1])*(s[j]-s[i+1]);
	};
	auto ans=enumerate_monge_shortest_path(n+1,cost);
	for(int i=n;i>=1;i--)cout<<ans[i]<<endl;
}
0