제출 #966322

#제출 시각아이디문제언어결과실행 시간메모리
966322MisterReaper수열 (APIO14_sequence)C++17
33 / 100
2032 ms131072 KiB
#include <bits/stdc++.h> using i64 = long long; struct line { i64 a, b; line(i64 _a, i64 _b) : a(_a), b(_b) {} long double intersect(line rhs) { return (long double)(b - rhs.b) / (rhs.a - a); } i64 eval(i64 x) { return a * x + b; } bool operator== (line rhs) { return a == rhs.a && b == rhs.b; } }; namespace std { std::string to_string(line l) { return '(' + to_string(l.a) + "x + " + to_string(l.b) + ')'; } }; #ifdef DEBUG #include "debug.h" #else #define debug(...) void(23) #endif constexpr int maxN = 1E5 + 5; constexpr int maxK = 200 + 5; int A[maxN], go[maxK][maxN]; i64 dp[maxK][maxN], p[maxN]; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, K; std::cin >> N >> K; for(int i = 1; i <= N; i++) { std::cin >> A[i]; } for(int i = 1; i <= N; i++) { p[i] = p[i - 1] + A[i]; } std::deque<std::pair<line, int>> dq; auto size = [&]() -> int { return (int) dq.size(); }; auto Add = [&](line l, int idx) -> void { while(size() >= 2 && (l == dq[0].first || l.intersect(dq[0].first) >= dq[0].first.intersect(dq[1].first))) { dq.pop_front(); } if(size() && l == dq[0].first) { dq.pop_front(); } dq.emplace_front(l, idx); }; auto Query = [&](i64 x) -> std::pair<i64, int> { int l = 0, r = size() - 1; while(l < r) { int m = (l + r) >> 1; if(dq[m].first.eval(x) < dq[m + 1].first.eval(x)) { l = m + 1; } else { r = m; } } return {dq[l].first.eval(x), dq[l].second}; }; for(int k = 1; k <= K; k++) { dq.clear(); Add({0, 0}, 0); for(int i = 1; i <= N; i++) { // for(int j = 0; j < i; j++) { // if(dp[k - 1][j] + 1LL * (p[i] - p[j]) * (p[N] - p[i]) >= dp[k][i]) { // go[k][i] = j; // dp[k][i] = dp[k - 1][j] + 1LL * (p[i] - p[j]) * (p[N] - p[i]); // } // } auto [v, j] = Query(p[N] - p[i]); dp[k][i] = v + 1LL * p[i] * (p[N] - p[i]); go[k][i] = j; Add(line{-p[i], dp[k - 1][i]}, i); debug(dq); debug(k, i, dp[k][i], go[k][i]); } } int ans = 1; for(int i = 1; i < N; i++) { if(dp[K][i] >= dp[K][ans]) { ans = i; } } std::cout << dp[K][ans] << '\n'; std::vector<int> v; for(int k = K; k >= 1; k--) { v.emplace_back(ans); ans = go[k][ans]; } for(int i = K - 1; i >= 0; i--) { std::cout << v[i] << " \n"[i == 0]; } 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...