#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 11;
const ll is_query = -(1ll << 62);
ll n, k;
ll a[N], p[N], s[N], sz[201];
pair < ll, ll > ans;
pair < ll, ll > dp[N][201];
struct convex_hull{
ll l = 1, r;
struct line {
ll m, b, i;
ll get(ll x){
return m * x + b;
}
};
vector < line > c;
double slope(line a, line b){
return 1.0 * (b.b - a.b) / (a.m - b.m);
}
bool bad(line nw){
line x = c[c.size() - 2], y = c[c.size() - 1];
if((x.b - nw.b) * (y.m - x.m) == (x.b - y.b) * (nw.b - x.m)) return nw.b > y.b;
return (x.b - nw.b) * (y.m - x.m) < (x.b - y.b) * (nw.b - x.m);
}
pair < ll, ll > eval(ll x){
if(l >= c.size()) return {0, 0};
while(l + 1 < c.size() && c[l].get(x) < c[l + 1].get(x)) l++;
return {c[l].get(x), c[l].i};
}
void insert_line(line nw){
if(c.empty()) c.push_back({0, 0});
while(l + 1 < c.size() && bad(nw)) c.pop_back();
// for(auto it : c) cout << it.i << ' ' << it.m << '\n';
// cout << '\n';
c.push_back(nw);
}
} hull[201];
void solve(){
cin >> n >> k;
for(ll i = 0; i <= 200; i++) sz[i] = 1;
for(ll i = 1; i <= n; i++) cin >> a[i];
for(ll i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];
for(ll i = n; i >= 1; i--) s[i] = s[i + 1] + a[i];
hull[0].insert_line({0, 0, 0});
for(ll i = 1; i < n; i++){
for(ll lay = 1; lay <= min(i, k); lay++){
dp[i][lay] = hull[lay - 1].eval(-(s[i + 1]));
dp[i][lay].first += p[i] * s[i + 1];
// cout << i << ' ' << lay << ' ' << dp[i][lay].first << ' ' << dp[i][lay].second << '\n';
}
for(ll lay = 1; lay <= min(i, k); lay++){
hull[lay].insert_line({p[i], dp[i][lay].first, i});
if(dp[i][lay].first >= ans.first) ans = {dp[i][lay].first, i};
}
}
cout << ans.first << '\n';
while(k > 0){
cout << ans.second << ' ';
ans = dp[ans.second][k];
k--;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
# | 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... |