結果
| 問題 | No.952 危険な火薬庫 |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-16 04:08:59 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,816 ms / 2,000 ms |
| + 892µs | |
| コード長 | 9,933 bytes |
| 記録 | |
| コンパイル時間 | 4,410 ms |
| コンパイル使用メモリ | 357,004 KB |
| 実行使用メモリ | 362,112 KB |
| 最終ジャッジ日時 | 2026-11-16 04:09:23 |
| 合計ジャッジ時間 | 22,968 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
// 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);
for(int i=0;i<=n;i++){
vl v;
for(int j=i;j<=n;j++)v.push_back(s[j]);
cht[i].build(v);
}
vvl dp(n+2,vl(n+2));
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;
}