結果
| 問題 | No.952 危険な火薬庫 |
| ユーザー |
 ebi_fly
|
| 提出日時 | 2023-11-08 15:35:04 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,597 bytes |
| コンパイル時間 | 2,318 ms |
| コンパイル使用メモリ | 192,068 KB |
| 実行使用メモリ | 13,480 KB |
| 最終ジャッジ日時 | 2023-11-08 15:35:11 |
| 合計ジャッジ時間 | 6,500 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,480 KB |
| testcase_01 | AC | 2 ms
6,676 KB |
| testcase_02 | AC | 2 ms
6,676 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
ソースコード
#line 1 "template/template.hpp"
#include <algorithm>
#include <bit>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numbers>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)
#define Rep(i, a, n) for (i64 i = (i64)(a); i < (i64)(n); i++)
#define RRep(i, a, n) for (i64 i = ((i64)(n)-i64(1)); i >= (i64)(a); i--)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#line 2 "template/debug_template.hpp"
#line 4 "template/debug_template.hpp"
namespace ebi {
#ifdef LOCAL
#define debug(...) \
std::cerr << "LINE: " << __LINE__ << " [" << #__VA_ARGS__ << "]:", \
debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
void debug_out() {
std::cerr << std::endl;
}
template <typename Head, typename... Tail> void debug_out(Head h, Tail... t) {
std::cerr << " " << h;
if (sizeof...(t) > 0) std::cerr << " :";
debug_out(t...);
}
} // namespace ebi
#line 2 "template/int_alias.hpp"
#line 4 "template/int_alias.hpp"
namespace ebi {
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
} // namespace ebi
#line 2 "template/io.hpp"
#line 7 "template/io.hpp"
namespace ebi {
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa) {
return os << pa.first << " " << pa.second;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &os, std::pair<T1, T2> &pa) {
return os >> pa.first >> pa.second;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
for (std::size_t i = 0; i < vec.size(); i++)
os << vec[i] << (i + 1 == vec.size() ? "" : " ");
return os;
}
template <typename T>
std::istream &operator>>(std::istream &os, std::vector<T> &vec) {
for (T &e : vec) std::cin >> e;
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::optional<T> &opt) {
if (opt) {
os << opt.value();
} else {
os << "invalid value";
}
return os;
}
void fast_io() {
std::cout << std::fixed << std::setprecision(15);
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
} // namespace ebi
#line 2 "template/utility.hpp"
#line 5 "template/utility.hpp"
#line 7 "template/utility.hpp"
namespace ebi {
template <class T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T> T safe_ceil(T a, T b) {
if (a % b == 0)
return a / b;
else if (a >= 0)
return (a / b) + 1;
else
return -((-a) / b);
}
template <class T> T safe_floor(T a, T b) {
if (a % b == 0)
return a / b;
else if (a >= 0)
return a / b;
else
return -((-a) / b) - 1;
}
constexpr i64 LNF = std::numeric_limits<i64>::max() / 4;
constexpr int INF = std::numeric_limits<int>::max() / 2;
const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};
const std::vector<int> dx = {0, 1, 0, -1, 1, -1, 1, -1};
} // namespace ebi
#line 2 "algorithm/monge_d_edge_shortest_path.hpp"
#line 4 "algorithm/monge_d_edge_shortest_path.hpp"
#line 2 "algorithm/golden_section_search.hpp"
#line 4 "algorithm/golden_section_search.hpp"
#include <concepts>
#line 7 "algorithm/golden_section_search.hpp"
#line 9 "algorithm/golden_section_search.hpp"
namespace ebi {
// ref: https://x.com/noshi91/status/1399003086362865673
template <class S, class F,
class T = decltype(std::declval<F>()(std::declval<S>())),
class Compare = std::less<T>>
std::pair<S, T> golden_section_search(F f, S min, S max,
const Compare &compare = Compare()) {
assert(min <= max);
S a = min - 1, x, b;
{
S s = 1, t = 2;
while (t < max - min + 2) {
std::swap(s += t, t);
}
x = a + t - s;
b = a + t;
}
T fx = f(x), fy;
while (a + b != 2 * x) {
S y = a + b - x;
if (max < y || compare(fx, (fy = f(y)))) {
b = a;
a = y;
} else {
a = x;
x = y;
fx = fy;
}
}
return {x, fx};
}
} // namespace ebi
#line 2 "algorithm/monge_shortest_path.hpp"
#line 5 "algorithm/monge_shortest_path.hpp"
namespace ebi {
template <class F, class T = decltype(std::declval<F>()(std::declval<int>(),
std::declval<int>()))>
std::vector<T> monge_shortest_path(int n, F f) {
const T max = std::numeric_limits<T>::max();
std::vector<int> argmin(n, 0);
std::vector<T> dp(n, max);
dp[0] = 0;
auto get = [&](int i, int j) -> T {
T val = f(j, i);
if (val == max || dp[j] == max) return max;
return dp[j] + val;
};
auto check = [&](int i, int j) -> void {
T val = get(i, j);
if (val < dp[i]) {
dp[i] = val;
argmin[i] = j;
}
};
dp[n - 1] = get(n - 1, 0);
auto dfs = [&](auto &&self, int l, int r) -> void {
if (r - l == 1) return;
int m = (l + r) >> 1;
for (int i = argmin[l]; i <= argmin[r]; i++) {
check(m, i);
}
self(self, l, m);
for (int i = l + 1; i <= m; i++) {
check(r, i);
}
self(self, m, r);
};
dfs(dfs, 0, n - 1);
return dp;
}
} // namespace ebi
#line 7 "algorithm/monge_d_edge_shortest_path.hpp"
namespace ebi {
template <class F, class T = decltype(std::declval<F>()(std::declval<int>(),
std::declval<int>()))>
T monge_d_edge_shortest_path(int n, int d, T upper, F f) {
auto dp = [&](T x) -> T {
auto g = [&](int i, int j) -> T { return f(i, j) + x; };
T c = monge_shortest_path(n, g)[n - 1];
return c - x * d;
};
return golden_section_search(dp, -upper, upper, std::greater<T>()).second;
}
} // namespace ebi
#line 3 "a.cpp"
namespace ebi {
void main_() {
int n;
std::cin >> n;
std::vector<i64> a(n);
std::cin >> a;
a.insert(a.begin(), 0);
n++;
std::vector<i64> sum(n+1, 0);
rep(i,0,n) sum[i+1] = sum[i] + a[i];
auto f = [&](int i, int j) -> i128 {
return (sum[j] - sum[i+1]) * (sum[j] - sum[i+1]);
};
rrep(i,1,n) {
i64 ans = monge_d_edge_shortest_path(n+1, i, i128(1'000'000'000'000'000'000), f);
std::cout << ans << '\n';
}
}
} // namespace ebi
int main() {
ebi::fast_io();
int t = 1;
// std::cin >> t;
while (t--) {
ebi::main_();
}
return 0;
}