제출 #565535

#제출 시각아이디문제언어결과실행 시간메모리
565535Forested수열 (APIO14_sequence)C++17
71 / 100
70 ms131072 KiB
// ===== template.hpp ===== #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cmath> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i) #define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i) #define ALL(x) begin(x), end(x) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using u128 = __uint128_t; using i32 = signed int; using i64 = signed long long; using i128 = __int128_t; using f64 = double; using f80 = long double; template <typename T> using Vec = vector<T>; template <typename T> bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template <typename T> bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } istream &operator>>(istream &is, i128 &x) { i64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, i128 x) { os << (i64) x; return os; } istream &operator>>(istream &is, u128 &x) { u64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, u128 x) { os << (u64) x; return os; } template <typename F, typename Comp = less<>> Vec<i32> sort_index(i32 n, F f, Comp comp = Comp()) { Vec<i32> idx(n); iota(ALL(idx), 0); sort(ALL(idx), [&](i32 i, i32 j) -> bool { return comp(f(i), f(j)); }); return idx; } [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); } } fast_io; // ===== template.hpp ===== #ifdef DEBUGF #include "cpl/template/debug.hpp" #else #define DBG(x) (void) 0 #endif // ===== utils.hpp ===== constexpr bool is_prime(unsigned n) { if (n == 0 || n == 1) { return false; } for (unsigned i = 2; i * i <= n; ++i) { if (n % i == 0) { return false; } } return true; } constexpr unsigned mod_pow(unsigned x, unsigned y, unsigned mod) { unsigned ret = 1, self = x; while (y != 0) { if (y & 1) { ret = static_cast<unsigned>(static_cast<unsigned long long>(ret) * self % mod); } self = static_cast<unsigned>(static_cast<unsigned long long>(self) * self % mod); y /= 2; } return ret; } template <unsigned mod> constexpr unsigned primitive_root() { static_assert(is_prime(mod), "`mod` must be a prime number."); if (mod == 2) { return 1; } unsigned primes[32] = {}; int it = 0; { unsigned m = mod - 1; for (unsigned i = 2; i * i <= m; ++i) { if (m % i == 0) { primes[it++] = i; while (m % i == 0) { m /= i; } } } if (m != 1) { primes[it++] = m; } } for (unsigned i = 2; i < mod; ++i) { bool ok = true; for (int j = 0; j < it; ++j) { if (mod_pow(i, (mod - 1) / primes[j], mod) == 1) { ok = false; break; } } if (ok) return i; } return 0; } // y >= 1 template <typename T> constexpr T safe_mod(T x, T y) { x %= y; if (x < 0) { x += y; } return x; } // y != 0 template <typename T> constexpr T floor_div(T x, T y) { if (y < 0) { x *= -1; y *= -1; } if (x >= 0) { return x / y; } else { return -((-x + y - 1) / y); } } // y != 0 template <typename T> constexpr T ceil_div(T x, T y) { if (y < 0) { x *= -1; y *= -1; } if (x >= 0) { return (x + y - 1) / y; } else { return -(-x / y); } } // ===== utils.hpp ===== // monotone class CHT { deque<pair<i64, i64>> que; bool need(const pair<i64, i64> &a, const pair<i64, i64> &b, const pair<i64, i64> &c) const { assert(b.first != c.first); i64 ab = floor_div(b.second - a.second, a.first - b.first); i64 bc = floor_div(c.second - b.second, b.first - c.first); return ab < bc; } public: CHT() : que() {} void add(i64 a, i64 b) { if (!que.empty() && que.back().first == a) { if (que.back().second > b) { que.pop_back(); } else { return; } } que.emplace_back(a, b); while (que.size() >= 3) { if (!need(que[que.size() - 3], que[que.size() - 2], que[que.size() - 1])) { swap(que[que.size() - 2], que[que.size() - 1]); que.pop_back(); } else { break; } } } i64 get(i64 x) { assert(!que.empty()); while (que.size() >= 2) { i64 fi = que[0].first * x + que[0].second; i64 se = que[1].first * x + que[1].second; if (fi >= se) { que.pop_front(); } else { break; } } return que[0].first * x + que[0].second; } }; int main() { i32 n, k; cin >> n >> k; ++k; Vec<i64> a(n); REP(i, n) { cin >> a[i]; } Vec<i64> sum(n + 1, 0), sqsum(n + 1, 0); REP(i, n) { sum[i + 1] = sum[i] + a[i]; sqsum[i + 1] = sqsum[i] + a[i] * a[i]; } const auto product_sum = [&](i32 l, i32 r) -> i64 { i64 s = sum[r] - sum[l], sq = sqsum[r] - sqsum[l]; return (s * s - sq) / 2; }; Vec<Vec<i64>> dp(k + 1, Vec<i64>(n + 1, INF64)); dp[0][0] = 0; REP(i, 1, k + 1) { CHT cht; REP(j, i, n + 1) { /*REP(l, j) { chmin(dp[i][j], dp[i - 1][l] + (sum[l] * sum[l] + sqsum[l]) / 2 - sum[l] * sum[j]); } dp[i][j] += (sum[j] * sum[j] - sqsum[j]) / 2;*/ //if (dp[i - 1][j - 1] != INF64) cht.add(-sum[j - 1], dp[i - 1][j - 1] + (sum[j - 1] * sum[j - 1] + sqsum[j - 1]) / 2); dp[i][j] = cht.get(sum[j]) + (sum[j] * sum[j] - sqsum[j]) / 2; } } DBG(dp); i64 ans = product_sum(0, n) - dp[k][n]; Vec<i32> sps; sps.reserve(k); { i32 now = n; for (i32 i = k; i > 0; --i) { PER(j, now) { if (dp[i - 1][j] + product_sum(j, now) == dp[i][now]) { now = j; break; } } sps.push_back(now); } } reverse(ALL(sps)); cout << ans << '\n'; REP(i, 1, k) { cout << sps[i] << " \n"[i + 1 == k]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...