제출 #966193

#제출 시각아이디문제언어결과실행 시간메모리
966193Pring수열 (APIO14_sequence)C++17
71 / 100
66 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) using ll = long long; typedef pair<int, int> pii; const int MXN = 100005, MXM = 205; const ll INF = 3.9e18; int n, k, a[MXN]; ll pre[MXN]; ll dp[MXN][MXM]; int K[MXN][MXM]; struct MK { ll m, k, id; MK() {} MK(ll _m, ll _k, ll _id) : m(_m), k(_k), id(_id) {} ll operator()(int x) { return m * x + k; } double operator*(MK o) { return (double) (o.k - k) / (m - o.m); } }; deque<MK> dq; void POP(int x) { while (dq.size() >= 2) { MK L0 = dq[0], L1 = dq[1]; if (L0(x) < L1(x)) break; dq.pop_front(); } } void PUSH(MK L) { while (dq.size() >= 2) { MK L_1 = dq[dq.size() - 1], L_2 = dq[dq.size() - 2]; if (L_1.m == L.m) { if (L_1.k < L.k) return; dq.pop_back(); continue; } if (L_1 * L_2 < L * L_2) break; dq.pop_back(); } dq.push_back(L); } void DP(int id) { dq.push_back(MK(0, INF, 0)); FOR(i, 1, n + 1) { POP(pre[i]); dp[i][id] = pre[i] * pre[i] + dq.front()(pre[i]); K[i][id] = dq.front().id; PUSH(MK(-2 * pre[i], dp[i][id - 1] + pre[i] * pre[i], i)); } dq.clear(); } vector<int> BT() { int now = n; vector<int> v; for (int i = k + 1; i > 1; i--) { v.push_back(K[now][i]); now = K[now][i]; } return v; } void miku() { cin >> n >> k; FOR(i, 1, n + 1) cin >> a[i]; FOR(i, 1, n + 1) pre[i] = pre[i - 1] + a[i]; FOR(i, 1, n + 1) dp[i][1] = pre[i] * pre[i]; FOR(i, 2, k + 2) DP(i); // FOR(id, 1, k + 2) { // FOR(i, 1, n + 1) cout << dp[i][id] << ' '; // cout << '\n'; // } // cout << '\n'; cout << (pre[n] * pre[n] - dp[n][k + 1]) / 2 << '\n'; vector<int> ans = BT(); for (auto &i : ans) cout << i << ' '; cout << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }
#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...