結果
問題 |
No.952 危険な火薬庫
|
ユーザー |
![]() |
提出日時 | 2025-05-15 23:10:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,568 ms / 2,000 ms |
コード長 | 7,993 bytes |
コンパイル時間 | 3,941 ms |
コンパイル使用メモリ | 320,720 KB |
実行使用メモリ | 295,652 KB |
最終ジャッジ日時 | 2025-05-15 23:11:03 |
合計ジャッジ時間 | 15,701 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } using pint = pair<int, int>; using pll = pair<long long, long long>; using tint = array<int, 3>; using tll = array<long long, 3>; using fint = array<int, 4>; using fll = array<long long, 4>; using vint = vector<int>; using vll = vector<long long>; using ll = long long; using u32 = unsigned int; using u64 = unsigned long long; template <class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PB push_back #define MP make_pair #define MT make_tuple #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // debug stream template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, deque<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template<class T> ostream& operator << (ostream &s, set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, multiset<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } /*///////////////////////////////////////////////////////*/ // Utility /*///////////////////////////////////////////////////////*/ // 4-neighbor const vector<int> dx = {1, 0, -1, 0}; const vector<int> dy = {0, 1, 0, -1}; // 8-neighbor const vector<int> dx8 = {1, 0, -1, 0, 1, -1, 1, -1}; const vector<int> dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; // bit int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } // xor128による乱数生成、周期は2^128-1 unsigned int randInt() { static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123; unsigned int tt = (tx^(tx<<11)); tx = ty; ty = tz; tz = tw; return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) ); } int randInt(int minv, int maxv) { return randInt() % (maxv - minv + 1) + minv; } ll randll(ll minv, ll maxv) { ll a = randInt(), b = randInt(); return (a * (1LL<<29) + b) % (maxv - minv + 1) + minv; } template<class T> void shuffle(vector<T>& vec) { int n = vec.size(); for (int i = n - 1; i > 0; --i) { int k = randInt() % (i + 1); swap(vec[i], vec[k]); } } // floor, ceil template<class T> T floor(T a, T b) { if (a % b == 0 || a >= 0) return a / b; else return -((-a) / b) - 1; } template<class T> T ceil(T x, T y) { return floor(x + y - 1, y); } // kth root // N < 2^64, K <= 64 uint64_t kth_root(uint64_t N, uint64_t K) { assert(K >= 1); if (N <= 1 || K == 1) return N; if (K >= 64) return 1; if (N == uint64_t(-1)) --N; auto mul = [&](uint64_t x, uint64_t y) -> uint64_t { if (x < UINT_MAX && y < UINT_MAX) return x * y; if (x == uint64_t(-1) || y == uint64_t(-1)) return uint64_t(-1); return (x <= uint64_t(-1) / y ? x * y : uint64_t(-1)); }; auto power = [&](uint64_t x, uint64_t k) -> uint64_t { if (k == 0) return 1ULL; uint64_t res = 1ULL; while (k) { if (k & 1) res = mul(res, x); x = mul(x, x); k >>= 1; } return res; }; uint64_t res; if (K == 2) res = sqrtl(N) - 1; else if (K == 3) res = cbrt(N) - 1; else res = pow(N, nextafter(1 / double(K), 0)); while (power(res + 1, K) <= N) ++res; return res; } // int 128 using i128 = __int128; constexpr i128 to_integer(const string &s) { i128 res = 0; for (auto c : s) { if (isdigit(c)) res = res * 10 + (c - '0'); } if (s[0] == '-') res *= -1; return res; } istream& operator >> (istream &is, i128 &x) { string s; is >> s; x = to_integer(s); return is; } ostream& operator << (ostream &os, const i128 &x) { i128 ax = (x >= 0 ? x : -x); char buffer[128]; char *d = end(buffer); do { --d; *d = "0123456789"[ax % 10]; ax /= 10; } while (ax != 0); if (x < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); } return os; } // Convex Hull Trick /* 追加クエリの直線の傾きが単調減少の場合 - insert (a, b): add y = ax + b - query (x): min_i{a[i]*x + b} */ template<class T> struct CHT { using Line = pair<T, T>; deque<Line> lines; inline bool check(const Line &a, const Line &b, const Line &c) { return (b.first - a.first) * (c.second - b.second) >= (b.second - a.second) * (c.first - b.first); } inline T get(int k, T x) { if (lines.empty() || k >= lines.size()) return i128(1) << 66; assert(k >= 0 && k < lines.size()); return lines[k].first * x + lines[k].second; } void insert(T a, T b) { Line l(a, b); while (lines.size() >= 2 && check(lines[(int)lines.size()-2], lines[(int)lines.size()-1], l)) { lines.pop_back(); } lines.push_back(l); } T query(T x) { int low = -1, high = (int)lines.size(); while (high - low > 1) { int mid = (low + high) / 2; if (get(mid, x) >= get(mid + 1, x)) low = mid; else high = mid; } return get(high, x); } // クエリの単調性も成り立つ場合 (x が単調増加) T query_monotone(T x) { while (lines.size() >= 2 && get(0, x) >= get(1, x)) lines.pop_front(); if (lines.empty()) return i128(1) << 66; return lines[0].first * x + lines[0].second; } }; int main() { int N; cin >> N; N++; vector<i128> A(N, 0), S(N+1, 0); REP(i, N) { if (i) cin >> A[i]; S[i+1] = S[i] + A[i]; } vector chts(N+1, CHT<i128>()); i128 INF = i128(1)<<100; vector dp(N+1, vector(N+1, INF)); auto push = [&](int i, int j) -> void { if (i-1 >= 0) chts[i-j].insert(-S[i]*2, S[i]*S[i] + dp[i-1][j]); }; dp[0][0] = 0; push(0, 0); REP2(i, 1, N+1) { REP(j, i) { chmin(dp[i][j], dp[i-1][j]); /* chmin(dp[i][j], dp[i-j-1][0] + S[i]² - 2S[i-j]S[i] + S[i-j]²) chmin(dp[i][j], dp[i-j][1] + S[i]² - 2S[i-j-1]S[i] + S[i-j-1]²) ... chmin(dp[i][j], dp[i-2][j-1] + S[i]² - 2S[i-1]S[i] + S[i-1]²) */ // REP(k, j) { // chmin(dp[i][j], dp[i-j-1+k][k] + (S[i] - S[i-j+k]) * (S[i] - S[i-j+k])); // } chmin(dp[i][j], chts[i-j].query(S[i]) + S[i] * S[i]); push(i, j); } } REP2(k, 1, N) { cout << dp[N][k] << endl; } }