제출 #971166

#제출 시각아이디문제언어결과실행 시간메모리
971166kilkuwu수열 (APIO14_sequence)C++17
50 / 100
2043 ms24640 KiB
#include <bits/stdc++.h> #define nl '\n' const int mxN = 1e4 + 5, mxK = 205; int A[mxN]; int64_t pref[mxN], dp[mxN][mxK]; int way[mxN][mxK]; int N, K; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> K; for (int i = 1; i <= N; i++) { std::cin >> A[i]; pref[i] = pref[i - 1] + A[i]; } memset(dp, -0x3f, sizeof(dp)); dp[0][0] = 0; for (int i = 1; i <= N; i++) { int to = std::min(i, K + 1); for (int j = 1; j <= to; j++) { for (int k = i - 1; k >= 0; k--) { auto cand = dp[k][j - 1] + (pref[i] - pref[k]) * pref[k]; if (dp[i][j] < cand) { dp[i][j] = cand; way[i][j] = k; } } } } std::cout << dp[N][K + 1] << 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...