이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100000 + 5;
const int KMAX = 200 + 5;
typedef long long int lint;
const lint INF = 2E18;
int N, K;
int sPart[NMAX];
pair <lint, int> dpBrute[KMAX][NMAX];
int father[KMAX][NMAX];
void brute() {
dpBrute[1][0] = {INF, 0};
for (int j = 1; j <= N; ++ j)
dpBrute[1][j] = {1LL * sPart[j] * sPart[j], 0};
for (int i = 2; i <= K; ++ i) {
dpBrute[i][0] = {INF, 0};
for (int j = 1; j <= N; ++ j) {
dpBrute[i][j] = {1LL * (sPart[j] - sPart[j - 1]) * (sPart[j] - sPart[j - 1]) + dpBrute[i - 1][j - 1].first, j - 1};
for (int k = 1; k <= j; ++ k)
dpBrute[i][j] = min(dpBrute[i][j], {1LL * (sPart[j] - sPart[k - 1]) * (sPart[j] - sPart[k - 1]) + dpBrute[i - 1][k - 1].first, k - 1});
}
}
}
int main()
{
//freopen("data.in", "r", stdin);
cin >> N >> K;
++ K;
for (int i = 1; i <= N; ++ i) {
int val;
cin >> val;
sPart[i] = val + sPart[i - 1];
}
brute();
cout << (1LL * sPart[N] * sPart[N] - dpBrute[K][N].first) / 2 << '\n';
vector <int> sol;
int where = N;
int k = K;
while (dpBrute[k][where].second) {
sol.push_back(dpBrute[k][where].second);
where = dpBrute[k --][where].second;
}
reverse(sol.begin(), sol.end());
for (int i = 0; i < sol.size(); ++ i)
cout << sol[i] << " \n"[i + 1 == sol.size()];
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sol.size(); ++ i)
^
sequence.cpp:55:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
cout << sol[i] << " \n"[i + 1 == sol.size()];
^
# | 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... |