#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
typedef struct Line{
ll p, q;
}line;
int n, k;
ll a[100005];
ll s[100005]={};
int track[205][100005];
line cht[100005];
ll sz=0;
ll now=0;
double cx(line a, line b)
{
return 1.0*(double)(b.q-a.q)/(a.p-b.p);
}
void insert(line v)
{
cht[sz]=v;
while(sz>1&&cx(cht[sz-2], cht[sz-1])>cx(cht[sz], cht[sz-1]))
{
cht[sz-1]=cht[sz];
sz--;
}
sz++;
}
pair <ll, ll> sol(ll x)
{
while(now<sz-1&&cx(cht[now], cht[now+1])<=x) now++;
return {cht[now].p*x+cht[now].q, now};
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
ll dp[k+1][n+1];
for(int i=0; i<=k; i++)
{
for(int j=0; j<=n; j++) dp[i][j]=0;
}
ll t;
for(int i=1; i<=n; i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
line l;
for(int i=1; i<=k; i++)
{
l.p=0;
l.q=0;
insert(l);
for(int j=1; j<=n; j++)
{
pair <ll, ll> p=sol(s[j]);
dp[i][j]=p.first;
track[i][j]=p.second;
l.p=s[j];
l.q=dp[i-1][j]-s[j]*s[j];
insert(l);
}
sz=0;
now=0;
}
cout<<dp[k][n]<<'\n';
vector <int> ans;
ll cur=n;
for(int i=k; i>=1; i--)
{
ans.push_back(track[i][cur]);
cur=track[i][cur];
}
reverse(ans.begin(), ans.end());
for(auto i:ans) cout<<i<<' ';
}
Compilation message
sequence.cpp: In function 'int main()':
sequence.cpp:43:5: warning: unused variable 't' [-Wunused-variable]
43 | ll t;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Incorrect |
0 ms |
384 KB |
Integer 0 violates the range [1, 1] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
contestant didn't find the optimal answer: 252308 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Integer 0 violates the range [1, 199] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Integer 0 violates the range [1, 999] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
1152 KB |
contestant didn't find the optimal answer: 1187850 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
7808 KB |
contestant didn't find the optimal answer: 5054352 < 19795776960 |
2 |
Halted |
0 ms |
0 KB |
- |