#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 320;
int n, K;
ll a[N];
ll dp[N][2];
int trace[202][N];
ll pre[N];
struct LINE {
ll a, b, id ;
LINE (ll a, ll b, ll id ) : a(a), b(b), id(id) {}
ll operator() (const ll &x) {
return a * x + b;
}
};
struct convex_hull_trick {
vector<LINE> op;
void init () {
vector<LINE> ().swap(op);
}
bool bad (LINE ln1, LINE ln2, LINE ln3) {
return (long double)(ln3.b - ln1.b) / (ln1.a - ln3.a) <= (long double)(ln2.b - ln1.b) / (ln1.a - ln2.a);
}
void add (LINE ln) {
while (SZ(op) >= 2 && bad(op[SZ(op) - 2], op[SZ(op) - 1], ln)) {
op.pop_back();
}
op.push_back(ln);
}
pll get (ll x) {
if (op.empty()) return MP(INF, 0);
ll lf = 0, rt = SZ(op) - 1;
while (lf < rt) {
ll mid = (lf + rt) >> 1;
if (op[mid](x) <= op[mid + 1](x)) rt = mid;
else lf = mid + 1;
}
return MP(op[lf](x), op[lf].id);
}
}cht;
void solution () {
cin >> n >> K;
rep (i, 1, n) cin >> a[i];
rep (i, 1, n) pre[i] = pre[i - 1] + a[i];
rep (i, 1, n) dp[i][1] = 0;
rep (k, 2, K) {
cht.init();
rep (i, 1, n) {
pll cur = cht.get(pre[i]);
dp[i][k & 1] = -cur.fs;
trace[k][i] = cur.se;
// cout << i <<" "<<k<<" "<<cur.fs<<" "<<cur.se <<"\n";
if (dp[i][k & 1] < INF)
cht.add(LINE(-pre[i], -(dp[i][k & 1 ^ 1] - pre[i] * pre[i]), i));
}
}
ll res = 0;
int opt = 0;
rep (i, K + 1, n) {
if (res < dp[i][K & 1] + (pre[n] - pre[i]) * pre[i]) {
res = dp[i][K & 1] + (pre[n] - pre[i]) * pre[i];
opt = i;
}
}
vector<int> Ans;
reb (k, K, 1) {
Ans.push_back(opt);
opt = trace[k][opt];
}
cout << res <<"\n";
iter (&id, Ans) cout << id<<" ";
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("TREEV");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9
7 3
4 1 3 4 0 2 3
*/
Compilation message
sequence.cpp: In function 'void solution()':
sequence.cpp:87:49: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
87 | cht.add(LINE(-pre[i], -(dp[i][k & 1 ^ 1] - pre[i] * pre[i]), i));
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
1 ms |
4440 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Incorrect |
0 ms |
2396 KB |
Integer 0 violates the range [1, 1] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 1093956 == 1093956 |
| 2 |
Incorrect |
0 ms |
4444 KB |
contestant didn't find the optimal answer: 302420312 < 302460000 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4444 KB |
contestant found the optimal answer: 610590000 == 610590000 |
| 2 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 311731167 < 311760000 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 21503404 == 21503404 |
| 2 |
Correct |
0 ms |
4444 KB |
contestant found the optimal answer: 140412195 == 140412195 |
| 3 |
Correct |
13 ms |
80496 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
| 4 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
| 5 |
Correct |
13 ms |
80484 KB |
contestant found the optimal answer: 679388326 == 679388326 |
| 6 |
Correct |
11 ms |
70236 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
| 7 |
Correct |
13 ms |
80520 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
| 8 |
Correct |
13 ms |
80476 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
| 9 |
Correct |
3 ms |
18992 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
| 10 |
Correct |
6 ms |
35164 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4960 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
| 2 |
Correct |
2 ms |
4956 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
| 3 |
Correct |
131 ms |
81480 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
| 4 |
Correct |
2 ms |
5224 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
| 5 |
Correct |
87 ms |
52168 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
| 6 |
Correct |
86 ms |
60312 KB |
contestant found the optimal answer: 514790755404 == 514790755404 |
| 7 |
Correct |
102 ms |
62672 KB |
contestant found the optimal answer: 1256105310476641 == 1256105310476641 |
| 8 |
Correct |
81 ms |
52492 KB |
contestant found the optimal answer: 3099592898816 == 3099592898816 |
| 9 |
Correct |
94 ms |
60580 KB |
contestant found the optimal answer: 1241131419367412 == 1241131419367412 |
| 10 |
Correct |
122 ms |
75200 KB |
contestant found the optimal answer: 1243084101967798 == 1243084101967798 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
13628 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
| 2 |
Correct |
21 ms |
13432 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
| 3 |
Correct |
1592 ms |
88076 KB |
contestant found the optimal answer: 497313449256899208 == 497313449256899208 |
| 4 |
Correct |
22 ms |
14044 KB |
contestant found the optimal answer: 374850090734572421 == 374850090734572421 |
| 5 |
Correct |
1659 ms |
87516 KB |
contestant found the optimal answer: 36183271951 == 36183271951 |
| 6 |
Correct |
962 ms |
65060 KB |
contestant found the optimal answer: 51629847150471 == 51629847150471 |
| 7 |
Correct |
1232 ms |
71400 KB |
contestant found the optimal answer: 124074747024496432 == 124074747024496432 |
| 8 |
Correct |
1012 ms |
59660 KB |
contestant found the optimal answer: 309959349080800 == 309959349080800 |
| 9 |
Correct |
1133 ms |
67456 KB |
contestant found the optimal answer: 124113525649823701 == 124113525649823701 |
| 10 |
Correct |
1436 ms |
81924 KB |
contestant found the optimal answer: 124309619349406845 == 124309619349406845 |
