# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1255254 | duybinhbeo | Split the sequence (APIO14_sequence) | C++20 | 182 ms | 158784 KiB |
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int dp[100001][201];
int a[100001];
int b[100001];
int trace[100001][201];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("inp.txt","r",stdin);
freopen("out.txt","w",stdout);
int n,k; cin >> n >> k;
for (int i = 1; i <= n; ++i){
cin >> a[i];
b[i]=b[i-1]+a[i];
}
for (int j = 2; j <= k+1; ++j){
for (int i = 1; i <= n; ++i){
for (int q = 1; q < i; ++q){
if (dp[i][j] <= dp[q][j-1]+b[q]*(b[i]-b[q])){
dp[i][j] = max(dp[i][j],dp[q][j-1]+b[q]*(b[i]-b[q]));
trace[i][j] = q;
}
}
}
}
cout << dp[n][k+1] << '\n';
int d = k+1,u = n;
vector<int>ans;
while (d > 1){
ans.push_back(trace[u][d]);
u = trace[u][d]; --d;
}
reverse(ans.begin(),ans.end());
for (int i : ans) cout << i << ' ';
}
Compilation message (stderr)
# | 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... |