이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }
#define int long long
const int mxk = 22;
const int mxn = 1010;
const int gay = 1e18;
int dp[mxn][mxk], a[mxn], n;
int ls[mxn][mxk], p[mxn], k;
int kv(int a) { return a * a; }
signed main() {
cin >> n >> k;
if(n > mxn) return 1;
for(int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++) {
dp[i][j] = gay;
if(j == 0)
dp[i][j] = p[i] * p[i];
}
for(int cur = 2; cur <= n; cur++)
for(int las = 1; las < cur; las++) {
int las_sum = p[cur] - p[las];
for(int j = 0; j < k && dp[las][j] != gay; j++) {
int CMP = dp[las][j] + las_sum * las_sum;
if(dp[cur][j + 1] == gay || dp[cur][j + 1] >= CMP) {
dp[cur][j + 1] = CMP;
ls[cur][j + 1] = las;
}
}
}
for(int i = 2; i <= n; i++)
for(int j = 1; j <= k; j++)
for(int t = 1; t < i; t++) {
if(dp[i][j] > dp[t][j - 1] + kv(p[i] - p[j - 1])) {
dp[i][j] = dp[t][j - 1] + kv(p[i] - p[j - 1]);
ls[i][j] = t;
}
}
int t = (p[n] * p[n] - dp[n][k]) / 2;
cout << t << endl;
for(int i = k; i >= 0; i--) {
n = ls[n][i];
if(n > 0)
cout << n << ' ';
}
return 0;
}
# | 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... |