#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort(all((x)))
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define SZ(x) ll(x.size())
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const ll MAXN = 1e5 + 10;
const ll MAXK = 210;
const ll LOG = 22;
const ll INF = 2e18;
const ll MOD = 2e9 + 7; // 998244353; // 1e9 + 9;
ll n , k , ptr , A[MAXN] , ps[MAXN] , dp[2][MAXN];
int prv[MAXK][MAXN];
vector<pair<pll , pll>> vec;
ll insect(pll A , pll B){
ll x = B.Y - A.Y , y = A.X - B.X;
if(A.X == B.X) return (A.Y <= B.Y ? -MOD : MOD);
if(y < 0) y *= -1 , x *= -1;
return (x / y + (x % y > 0));
}
void insert(ll A , ll B , ll ind){
ll pos = -MOD;
while(SZ(vec)){
ll x = insect(vec.back().Y , pll(A , B));
pos = max(x , vec.back().X.X);
if(x > vec.back().X.X) break;
vec.pop_back();
}
if(SZ(vec)) assert(pos > vec.back().X.X);
ptr = min(ptr , max(0ll , SZ(vec) - 1));
vec.push_back({{pos , ind} , {A , B}});
}
pll get(ll pos){
ptr = min(ptr , max(0ll , SZ(vec) - 2));
while(ptr + 1 < SZ(vec) && vec[ptr + 1].X.X <= pos) ptr++;
return {vec[ptr].Y.X * pos + vec[ptr].Y.Y , vec[ptr].X.Y};
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> k;
for(int i = 1 ; i <= n ; i++){
cin >> A[i];
ps[i] = ps[i - 1] + A[i];
}
//cout << (-2 / 3) << endl;
//cout << (-2 % 3) << endl;
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= n ; j++){
insert(ps[j - 1] , dp[1 - i % 2][j - 1] - ps[j - 1] * ps[j - 1] , j - 1);
pll A = get(ps[j]);
dp[i % 2][j] = A.X;
prv[i][j] = A.Y;
}
vec = {}; ptr = 0;
}
cout << dp[k % 2][n] << endl;
vector<int> ans;
int cur = prv[k][n] , ind = k - 1;
while(cur){
ans.push_back(cur);
cur = prv[ind][cur];
ind--;
}
reverse(all(ans));
for(int i : ans) cout << i << sep;
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
1 ms |
388 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
1 ms |
396 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
2 ms |
492 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
1 ms |
492 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
3 ms |
1536 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
2 ms |
1132 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
3 ms |
1260 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
3 ms |
1388 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 193556962 == 193556962 |
9 |
Correct |
1 ms |
492 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
10 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
1 ms |
492 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
9 ms |
2156 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
2 ms |
492 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
13 ms |
2156 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
7 ms |
1900 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
7 ms |
2156 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
6 ms |
2156 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
2 ms |
748 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
4 ms |
1132 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1136 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Correct |
2 ms |
1136 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
3 |
Correct |
64 ms |
9964 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
4 |
Correct |
4 ms |
1264 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
5 |
Correct |
45 ms |
6256 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
6 |
Correct |
51 ms |
7152 KB |
contestant found the optimal answer: 514790755404 == 514790755404 |
7 |
Correct |
50 ms |
7672 KB |
contestant found the optimal answer: 1256105310476641 == 1256105310476641 |
8 |
Correct |
38 ms |
6380 KB |
contestant found the optimal answer: 3099592898816 == 3099592898816 |
9 |
Correct |
48 ms |
7276 KB |
contestant found the optimal answer: 1241131419367412 == 1241131419367412 |
10 |
Correct |
61 ms |
8940 KB |
contestant found the optimal answer: 1243084101967798 == 1243084101967798 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
7272 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
2 |
Correct |
28 ms |
7264 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
3 |
Correct |
723 ms |
85080 KB |
contestant found the optimal answer: 497313449256899208 == 497313449256899208 |
4 |
Correct |
27 ms |
7924 KB |
contestant found the optimal answer: 374850090734572421 == 374850090734572421 |
5 |
Correct |
779 ms |
84380 KB |
contestant found the optimal answer: 36183271951 == 36183271951 |
6 |
Correct |
502 ms |
60884 KB |
contestant found the optimal answer: 51629847150471 == 51629847150471 |
7 |
Correct |
569 ms |
65500 KB |
contestant found the optimal answer: 124074747024496432 == 124074747024496432 |
8 |
Correct |
459 ms |
54440 KB |
contestant found the optimal answer: 309959349080800 == 309959349080800 |
9 |
Correct |
445 ms |
61284 KB |
contestant found the optimal answer: 124113525649823701 == 124113525649823701 |
10 |
Correct |
574 ms |
76892 KB |
contestant found the optimal answer: 124309619349406845 == 124309619349406845 |