제출 #715233

#제출 시각아이디문제언어결과실행 시간메모리
715233four_specks수열 (APIO14_sequence)C++17
38 / 100
665 ms98792 KiB
#include <bits/stdc++.h> using namespace std; namespace { template <typename T> T fl_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); } } // namespace struct Line { long m, c; int id; long operator()(long x) const { return m * x + c; } }; long isect(const Line &l1, const Line &l2) { return fl_div(l1.c - l2.c, l2.m - l1.m); } void solve() { int n, k; cin >> n >> k, ++k; vector<long> a(n); for (long &x : a) cin >> x; vector<long> pref(n + 1); for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i]; vector prv(n + 1, vector(k + 1, -1)); vector<deque<Line>> dp(k + 1); dp[0].push_back({0, 0, 0}); for (int i = 0; i < n; i++) { if (a[i] == 0) { for (int j = 0; j < k; j++) prv[i + 1][j + 1] = i; continue; } for (int j = 0; j < k; j++) { while ((int)dp[j].size() >= 2 && dp[j][1](pref[i + 1]) >= dp[j][0](pref[i + 1])) dp[j].pop_front(); prv[i + 1][j + 1] = min(dp[j][0].id, i); Line line = {pref[i + 1], dp[j][0](pref[i + 1]) - pref[i + 1] * pref[i + 1], i + 1}; while ((int)dp[j + 1].size() >= 2 && isect(line, dp[j + 1].back()) <= isect(dp[j + 1].back(), dp[j + 1].end()[-2])) dp[j + 1].pop_back(); dp[j + 1].push_back(line); } } long res = dp[k].back().c + pref[n] * pref[n]; vector<int> pos; for (int i = prv[n][k], j = k; i > 0; i = prv[i][--j]) pos.push_back(i); reverse(pos.begin(), pos.end()); cout << res << '\n'; for (int i : pos) cout << i << ' '; cout << '\n'; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); solve(); 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...