This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef ON_PC
freopen("input.txt", "r", stdin);
#endif
// freopen("output.txt", "w", stdout);
int T = 1;
// cin >> T;
while (T--){
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
vector<ll> pref(n + 1);
for (int i = 1; i <= n; i++){
pref[i] = pref[i - 1] + a[i];
}
vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -1e18));
vector<vector<int>> p(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++){
dp[i][0] = 0;
}
for (int cnt = 1; cnt <= k; cnt++){
for (int i = 1; i <= n; i++){
for (int j = i - 1; j >= 1; j--){
if (dp[j][cnt - 1] != -1e18 &&
dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]) >= dp[i][cnt]){
p[i][cnt] = j;
dp[i][cnt] = max(dp[i][cnt], dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]));
}
}
}
}
int v = 1;
for (int i = 1; i <= n; i++){
if (dp[i][k] > dp[v][k]){
v = i;
}
}
cout << dp[v][k] << "\n";
vector<int> res;
for (int cnt = k; cnt >= 1; cnt--){
res.push_back(p[v][cnt]);
v = p[v][cnt];
}
reverse(all(res));
for (int i = 0; i < k; i++){
cout << res[i] << " ";
}
cout << "\n";
// cout << dp[1][n][k] << "\n";
// vector<int> res;
// queue<array<int, 3>> q;
// q.push({1, n, k});
// while (!q.empty()){
// array<int, 3> t = q.front();
// q.pop();
// pair<int, int> w = p[t[0]][t[1]][t[2]];
// res.push_back(w.first);
// if (t[2]){
// q.push({t[0], w.first, w.second});
// q.push({w.first + 1, t[1], t[2] - 1 - w.second});
// }
// }
// assert(!res.empty());
// sort(all(res));
// for (int i = 0; i < res.size(); i++){
// if (res[i]){
// cout << res[i] << " ";
// }
// }
// 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... |