제출 #35739

#제출 시각아이디문제언어결과실행 시간메모리
35739waynetuinfor수열 (APIO14_sequence)C++14
28 / 100
2000 ms84604 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10, maxk = 200 + 5; 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 long inter(const line &rhs) const { return (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] = 0; int cur = 1; for (int i = 1; i <= k; ++i) { memset(dp[cur], 0, sizeof(dp[cur])); deque<line> dq; dq.push_back({ 0, dp[cur ^ 1][0], 0 }); for (int j = 1; j <= n; ++j) { while (dq.size() >= 2 && dq[1].checkfront(dq[0], s[j])) dq.pop_front(); dp[cur][j] = dq.front()(s[j]); t[i][j] = dq.front().i; 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; for (int i = 1; i <= k; ++i) { for (int j = 1; j <= n; ++j) { for (int p = 0; 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...