#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
struct Line{
ll a, b, c;
ll get(ll x){
return a*x+b;
}
};
struct CHT{
vector<Line> stk;
int idx = 1;
void insert(Line v){
if(stk.size() >= 1 && v.a == stk.back().a){
stk.back().a = v.a;
return;
}
while(stk.size() >= 2){
if((stk.back().b - v.b)*(stk.back().a - stk[stk.size()-2].a) < (v.a - stk.back().a)*(stk[stk.size()-2].b - v.b)){
stk.pop_back();
}else break;
}
if(stk.back().a == v.a && stk.back().b <= v.b && v.c) return;
stk.push_back(v);
}
p query(ll x){
while(idx+1 < stk.size() && (stk[idx].b - stk[idx+1].b) < (stk[idx+1].a - stk[idx].a) * x) idx++;
return {stk[idx].get(x), stk[idx].c};
}
};
ll arr[101010];
ll sum[101010];
ll dp[2][101010];
int track[222][101010];
vector<int> ans;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
for(int i=1; i<=n; i++) cin >> arr[i], sum[i] = sum[i-1] + arr[i];
for(int i=1; i<=k; i++){
CHT cht; cht.stk.reserve(101010); cht.insert({0, 0, 0});
for(int j=1; j<=n; j++){
auto now = cht.query(sum[j]);
dp[i&1][j] = now.x;
track[i][j] = now.y;
cht.insert({sum[j], dp[(i-1)&1][j] - sum[j]*sum[j], j});
}
}
cout << dp[k&1][n] << "\n";
int now = n;
ans.push_back(-1);
for(int i=1; i<=k; i++){
ans.push_back(track[k-i+1][now]);
now = track[k-i+1][now];
}
sort(all(ans));
for(int i=1; i<=k; i++){
if(!ans[i]) ans[i] = 1;
if(ans[i] <= ans[i-1]) ans[i] = ans[i-1] + 1;
}
for(int i=1; i<=k; i++) cout << ans[i] << " ";
}
Compilation message
sequence.cpp: In member function 'p CHT::query(ll)':
sequence.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx+1 < stk.size() && (stk[idx].b - stk[idx+1].b) < (stk[idx+1].a - stk[idx].a) * x) idx++;
~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Incorrect |
2 ms |
376 KB |
contestant didn't find the optimal answer: 774 < 999 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
contestant didn't find the optimal answer: 1093398 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
380 KB |
contestant didn't find the optimal answer: 314141646 < 610590000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
488 KB |
contestant didn't find the optimal answer: 21297372 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
872 KB |
contestant didn't find the optimal answer: 1482064300 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
4684 KB |
contestant didn't find the optimal answer: 14229199192 < 19795776960 |
2 |
Halted |
0 ms |
0 KB |
- |