제출 #971192

#제출 시각아이디문제언어결과실행 시간메모리
971192kilkuwu수열 (APIO14_sequence)C++17
71 / 100
2031 ms91476 KiB
#include <bits/stdc++.h> #define nl '\n' struct Line { mutable int64_t k, m, p; int id; bool operator<(const Line& o) const { return k < o.k; } bool operator<(int64_t x) const { return p < x; } }; struct LineContainer : std::multiset<Line, std::less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const int64_t inf = LLONG_MAX; int64_t div(int64_t a, int64_t b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(int64_t k, int64_t m, int id) { auto z = insert({k, m, 0, id}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } std::pair<int64_t, int> query(int64_t x) { assert(!empty()); auto l = *lower_bound(x); return {l.k * x + l.m, l.id}; } }; const int mxN = 1e5 + 5, mxK = 205; int way[mxN][mxK]; int N, K; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> K; std::vector<int> A(N + 1); std::vector<int64_t> pref(N + 1); for (int i = 1; i <= N; i++) { std::cin >> A[i]; pref[i] = pref[i - 1] + A[i]; } std::vector<int64_t> dp(N + 1, -1e18); std::vector<int64_t> ndp(N + 1, -1e18); dp[0] = 0; for (int j = 1; j <= K + 1; j++) { LineContainer lines; lines.add(pref[0], dp[0] - pref[0] * pref[0], 0); ndp[0] = -1e18; for (int i = 1; i <= N; i++) { auto line = lines.query(pref[i]); ndp[i] = line.first; way[i][j] = line.second; lines.add(pref[i], dp[i] - pref[i] * pref[i], i); } std::swap(dp, ndp); } std::cout << dp[N] << nl; std::vector<int> ans; int x = N; int y = K + 1; while (x > 0 && y > 1) { ans.push_back(way[x][y]); x = way[x][y]; y--; } for (int i : ans) std::cout << i << " "; std::cout << nl; } /* 7 3 4 1 3 4 0 2 3 */
#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...