제출 #35754

#제출 시각아이디문제언어결과실행 시간메모리
35754waynetuinfor수열 (APIO14_sequence)C++14
0 / 100
16 ms84608 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10, maxk = 200 + 5; const long long inf = 1e14; long long dp[2][maxn], s[maxn]; int t[maxk][maxn]; struct line { long long a, b; int i; long long operator()(const long long &x) const { return a * x + b; } bool checkfront(const line &rhs, const long long &x) const { return operator()(x) >= rhs(x); } long double inter(const line &rhs) const { return 1.0 * (rhs.b - b) / (a - rhs.a); } bool checkback(const line &rhs, const line &pivot) { return inter(pivot) >= rhs.inter(pivot); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; ++i) { int a; cin >> a; s[i] = s[i - 1] + a; } dp[0][0] = -inf; for (int i = 1; i <= n; ++i) dp[0][i] = 0; int cur = 1; for (int i = 1; i <= k; ++i) { // memset(dp[cur], 0, sizeof(dp[cur])); fill(dp[cur], dp[cur] + maxn, -inf); deque<line> dq; dq.push_back({ s[1], -s[1] * s[1], 1 }); // cout << "dp[" << i << "][" << 1 << "] = " << dp[cur][1] << endl; for (int j = 2; j <= n; ++j) { while (dq.size() >= 2 && dq[1].checkfront(dq[0], s[j])) dq.pop_front(); dp[cur][j] = dq.front()(s[j]); // cout << "dp[" << i << "][" << j << "] = " << dp[cur][j] << endl; t[i][j] = dq.front().i; // cout << "t[" << i << "][" << j << "] = " << t[i][j] << endl; line tmp = { s[j], dp[cur ^ 1][j] - s[j] * s[j], j }; while (dq.size() >= 2 && tmp.checkback(dq[dq.size() - 1], dq[dq.size() - 2])) dq.pop_back(); // if (dq.size() && dq.back().a == tmp.a && dq.back().b >= tmp.b) continue; dq.push_back(tmp); } cur ^= 1; } /* int cur = 1; dp[0][0] = -inf; for (int i = 1; i <= k; ++i) { fill(dp[cur], dp[cur] + maxn, -inf); for (int j = 1; j <= n; ++j) { for (int p = 1; p < j; ++p) { if (dp[cur ^ 1][p] + s[p] * (s[j] - s[p]) > dp[cur][j]) { dp[cur][j] = dp[cur ^ 1][p] + s[p] * (s[j] - s[p]); t[i][j] = p; } } } cur ^= 1; } */ cout << dp[cur ^ 1][n] << endl; stack<int> ans; int now = n; for (int i = k; i > 0; --i) { ans.push(t[i][now]); now = t[i][now]; } while (ans.size()) cout << ans.top() << ' ', ans.pop(); cout << endl; }
#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...