結果

問題 No.952 危険な火薬庫
ユーザー miscalc
提出日時 2025-09-03 03:52:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 983 ms / 2,000 ms
コード長 2,543 bytes
コンパイル時間 3,335 ms
コンパイル使用メモリ 285,144 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-03 03:52:56
合計ジャッジ時間 13,097 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
#define vc vector
using vl = vc<ll>;

#define ov(a, b, c, name, ...) name
#define rep2(i, l, r) for(ll i = (l); i < ll(r); i++)
#define rep1(i, n) rep2(i, 0, n)
#define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define fec(...) for(const auto& __VA_ARGS__)
#define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)

#define ALL(x) begin(x), end(x)
#define SZ(x) (ll) size(x)
#define LB(v, x) (lower_bound(ALL(v), x) - begin(v))
#define eb emplace_back

bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
const ll INF = ll(4e18) + 100;

void printvec(const auto& v) {
   for(auto it = begin(v); it != end(v); it++) cout << *it << " ";
   cout << endl;
}

#ifdef LOCAL
#define local(...) __VA_ARGS__
#else
#define local(...)
#endif

// monotone 行列の各行について、最小値を取る場所とその値を返す
template<typename T> vc<pair<int, T>> monotone_minima(int h, int w, auto f) {
   vc<pair<int, T>> dp(h, pair(-1, T()));
   auto rec = [&](auto&& rec, int u, int d, int l, int r) {
      if(u > d) return;
      int mid = (u + d) >> 1;
      auto& [idx, mi] = dp[mid];
      idx = l, mi = f(mid, l);
      rep(i, l + 1, r + 1) if(chmin(mi, f(mid, i))) idx = i;
      rec(rec, u, mid - 1, l, idx);
      rec(rec, mid + 1, d, idx, r);
   };
   rec(rec, 0, h - 1, 0, w - 1);
   return dp;
}

// 辺コストが monge である N 頂点 DAG の d 辺最短路を d=1,...,N について
vl monge_d_edge_enum(int N, auto f) {
   const ll INFL = 2 * INF + 100;
   vl ans(N + 1, INF), dp(N + 1, INFL);
   dp[0] = 0;
   rep(d, 1, N + 1) {
      auto mi = monotone_minima<ll>(N + 1, N + 1, [&](int j, int i) { return i < j ? dp[i] + f(i, j) : INFL; });
      per(i, N + 1, d) dp[i] = dp[mi[i].first] + f(mi[i].first, i);
      ans[d] = dp[N];
   }
  return ans;
}

int main() {
   cin.tie(0)->sync_with_stdio(0);

   ll N;
   cin >> N;
   vl A(N);
   rep(i, N) cin >> A.at(i);

   ll s = 0, l = 0, r = 0;
   auto add = [&](ll i) { s += A.at(i); };
   auto del = [&](ll i) { s -= A.at(i); };
   auto f = [&](ll L, ll R) -> ll {
      while(L < l) add(--l);
      while(r < R) add(r++);
      while(l < L) del(l++);
      while(R < r) del(--r);
      return s;
   };
   auto g = [&](ll i, ll j) -> ll {
      ll tmp = f(i, j - 1);
      return tmp * tmp;
   };

   auto ans = monge_d_edge_enum(N + 1, g);
   rep(k, 1, N + 1) cout << ans.at(N + 1 - k) << "\n";
}
0