結果
| 問題 | No.952 危険な火薬庫 |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-16 06:31:37 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 330 ms / 2,000 ms |
| + 67µs | |
| コード長 | 8,349 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
// 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;
}