제출 #1026996

#제출 시각아이디문제언어결과실행 시간메모리
1026996borisAngelov수열 (APIO14_sequence)C++17
50 / 100
2036 ms60808 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 10005; const int maxk = 205; const long long inf = 1e18; int n, k; long long a[maxn]; long long pref[maxn]; long long dp[maxn][maxk]; int prvState[maxn][maxn]; long long sum(int from, int to) { return pref[to] - pref[from - 1]; } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= min(i - 1, k); ++j) { dp[i][j] = -inf; prvState[i][j] = -1; for (int prv = i - 1; prv >= 1; --prv) { long long curr = dp[prv][j - 1] + sum(1, prv) * sum(prv + 1, i); if (dp[i][j] < curr) { dp[i][j] = curr; prvState[i][j] = prv; } } } } stack<int> splits; int pos = n; long long ans = dp[n][k]; while (k > 0) { splits.push(prvState[pos][k]); pos = splits.top(); --k; } cout << ans << endl; while (!splits.empty()) { cout << splits.top() << " "; splits.pop(); } cout << endl; return 0; } /* 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...