結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー askr58
提出日時 2026-11-16 03:59: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
結果
MLE  
実行時間 -
コード長 9,855 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,782 ms
コンパイル使用メモリ 355,396 KB
実行使用メモリ 587,648 KB
最終ジャッジ日時 2026-11-16 03:59:51
合計ジャッジ時間 13,467 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 3
other AC * 1 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

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>>>;
//https://qandori.github.io/cp-library/data_structure/li_chao_tree.hpp.html
#line 1 "data_structure/li_chao_tree.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template <class T = std::int64_t, bool maximize = false, class R = std::conditional_t<std::is_integral_v<T>, std::conditional_t<(sizeof(T) < 8), std::int64_t, __int128_t>, T>>
class LiChaoTree {
	static_assert((std::is_integral_v<T> && std::is_signed_v<T> && sizeof(T) <= 8) || std::is_floating_point_v<T>);
	struct Line {
		T a, b;
		template <class V>
		V eval(T x) const { return V(R(a) * R(x) + R(b)); }
	};
	int n = 0, base = 1;
	bool wide = false, dense = false;
	std::vector<T> xs;
	std::vector<Line> lines;
	std::vector<std::uint8_t> state;
	template <class V>
	static bool better(V a, V b) {
		if constexpr (maximize) return a > b;
		else return a < b;
	}
	template <class V>
	void insert(int k, int l, int width, Line f) {
		for (;;) {
			Line &g = lines[k];
			if (!(state[k] & 1)) {
				g = f;
				state[k] = 3;
				return;
			}
			if (f.a == g.a) {
				if (better(f.b, g.b)) g = f;
				return;
			}
			int half = width >> 1, m = l + half;
			if (better(f.template eval<V>(xs[m]), g.template eval<V>(xs[m]))) std::swap(f, g);
			if (!half) return;
			bool right = better(f.a, g.a);
			int edge = right ? l + width - 1 : l;
			if (!better(f.template eval<V>(xs[edge]), g.template eval<V>(xs[edge]))) return;
			k = k * 2 + right;
			if (right) l = m;
			width = half;
		}
	}
	template <class V>
	void insert_segment(int k, int l, int r, int ql, int qr, Line f) {
		if (ql <= l && r <= qr) {
			insert<V>(k, l, r - l, f);
			return;
		}
		if (state[k] & 1) {
			const Line &g = lines[k];
			if (f.a == g.a) {
				if (!better(f.b, g.b)) return;
			} else {
				int edge = better(f.a, g.a) ? std::min(r, qr) - 1 : std::max(l, ql);
				if (!better(f.template eval<V>(xs[edge]), g.template eval<V>(xs[edge]))) return;
			}
		}
		state[k] |= 2;
		int m = (l + r) >> 1;
		if (ql < m) insert_segment<V>(k * 2, l, m, ql, qr, f);
		if (m < qr) insert_segment<V>(k * 2 + 1, m, r, ql, qr, f);
	}

	void check(Line f, int l, int r) {
		if constexpr (std::is_integral_v<T> && std::is_same_v<R, __int128_t>) {
			if (!wide) {
				R a = f.template eval<R>(xs[l]), b = f.template eval<R>(xs[r - 1]);
				wide = a != R(std::int64_t(a)) || b != R(std::int64_t(b));
			}
		}
	}
	template <class F>
	decltype(auto) dispatch(F f) const {
		if constexpr (std::is_integral_v<T> && std::is_same_v<R, __int128_t>) {
			if (!wide) return f.template operator()<std::int64_t>();
		}
		return f.template operator()<R>();
	}

	int lower(T x) const {
		if (n <= 1) return n && xs[0] < x;
		if constexpr (std::is_integral_v<T>)
			if (dense) return int(std::clamp<__int128_t>(__int128_t(x) - xs[0], 0, n));
		int i = 0;
		for (int step = base >> 1; step; step >>= 1) i += int(xs[i + step - 1] < x) * step;
		return std::min(n, i + int(xs[i] < x));
	}

	template <class V>
	std::optional<R> query_impl(int i) const {
		assert(0 <= i && i < n);
		V result = maximize ? std::numeric_limits<V>::lowest() : std::numeric_limits<V>::max();
		bool found = false;
		for (int k = 1, bit = base >> 1;; bit >>= 1) {
			if (!state[k]) break;
			if (state[k] & 1) {
				V value = lines[k].template eval<V>(xs[i]);
				if ((std::is_floating_point_v<V> && !found) || better(value, result)) result = value;
				found = true;
			}
			if (!bit) break;
			k = k * 2 + bool(i & bit);
		}
		if (found) return result;
		return std::nullopt;
	}

  public:
	using value_type = R;
	explicit LiChaoTree(std::vector<T> coordinates = {}) { build(std::move(coordinates)); }
	void build(std::vector<T> coordinates) {
		if (!std::is_sorted(coordinates.begin(), coordinates.end())) std::sort(coordinates.begin(), coordinates.end());
		coordinates.erase(std::unique(coordinates.begin(), coordinates.end()), coordinates.end());
		assert(coordinates.size() <= std::size_t(1) << 29);
		n = static_cast<int>(coordinates.size());
		if constexpr (std::is_integral_v<T>) dense = n && __int128_t(coordinates.back()) - coordinates[0] == n - 1;
		base = int(std::bit_ceil(unsigned(std::max(1, n))));
		xs = std::move(coordinates);
		if (n) xs.resize(base, xs.back());
		lines.resize(base * 2);
		state.assign(base * 2, 0);
		wide = false;
	}
	int size() const { return n; }
	void clear() {
		std::fill(state.begin(), state.end(), 0);
		wide = false;
	}
	T coordinate(int i) const {
		assert(0 <= i && i < n);
		return xs[i];
	}
	int index(T x) const {
		int i = lower(x);
		assert(i < n && xs[i] == x);
		return i;
	}
	void add_line(T a, T b) {
		if (n) {
			Line f{a, b};
			check(f, 0, n);
			dispatch([&]<class V>() { insert<V>(1, 0, base, f); });
		}
	}
	void add_segment_index(int l, int r, T a, T b) {
		assert(0 <= l && l <= r && r <= n);
		if (l < r) {
			Line f{a, b};
			check(f, l, r);
			dispatch([&]<class V>() { insert_segment<V>(1, 0, base, l, r == n ? base : r, f); });
		}
	}
	void add_segment(T l, T r, T a, T b) {
		assert(l <= r);
		int left = lower(l);
		int right = lower(r);
		add_segment_index(left, right, a, b);
	}
	std::optional<R> query_index(int i) const {
		return dispatch([&]<class V>() { return query_impl<V>(i); });
	}
	std::optional<R> query(T x) const { return query_index(index(x)); }
};



int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	vl a(n);
	cin>>a;
	vl s(n+1);
	for(int i=0;i<n;i++)s[i+1]=s[i]+a[i];
	vector<LiChaoTree<ll>> cht(n+1,LiChaoTree<ll>(s));
	vvl dp(n+2,vl(n+1));
	cht[0].add_line(0,0);
	vl ans(n+1,1e18);
	for(int i=1;i<=n+1;i++){
		for(int j=i-1;j>=0;j--){
			dp[i][j+1]=cht[j].query(s[i-1]).value()+s[i-1]*s[i-1];
			if(i<=n)cht[j+1].add_line(-2*s[i],dp[i][j+1]+s[i]*s[i]);
			ans[i-j-1]=min(ans[i-j-1],dp[i][j+1]);
		}
		if(i<=n)ans[i]=min(ans[i],s[i]*s[i]);
		//cout<<dp[i]<<endl;
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
}

	
	
0