이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define nl '\n'
const int mxN = 1e5 + 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |