#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int, int> ii;
const int N = 1e5 + 5, oo = 1e18, K = 200;
int a[N], suf[N], pref[N], n, dp[2][N], trace[N][K];
struct Line {
int a, b, id;
Line() {}
Line(int _a, int _b, int _id) : a(_a), b(_b), id(_id) {}
int val(int x) {
return a * x + b;
}
};
struct CHT {
vector <Line> st;
CHT() {st.clear();}
bool bad(Line a, Line b, Line c) {
return (1.0 * (c.b - a.b) / (a.a - c.a) < 1.0 * (c.b - b.b) / (b.a - c.a));
}
void addLine(Line d) {
while (st.size() >= 2 && bad(d, st.back(), st[st.size() - 2])) {
// cerr << "delete Line y = " << st.back().a << "x + " << st.back().b << endl;
st.pop_back();
}
// cerr << "addLine y = " << d.a << "x + " << d.b << endl;
st.push_back(d);
}
ii query(int x) {
int l = 0, r = st.size() - 1, ans = -oo, id = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int cur = st[mid].val(x);
if (ans < cur) ans = max(ans, cur), id = st[mid].id;
if (mid != st.size() - 1 && st[mid + 1].val(x) > cur) l = mid + 1;
else if (mid != 0 && st[mid - 1].val(x) > cur) r = mid - 1;
else break;
}
return {ans, id};
}
};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("sequence.INP", "r", stdin);
// freopen("sequence.OUT", "w", stdout);
int k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + a[i];
}
memset(dp, -1, sizeof dp);
for (int i = 1; i <= n; ++i) {
dp[1][i] = pref[i] * (pref[n] - pref[i]);
}
// cerr << dp[1][1] << endl;
int res = -1, id = -1;
for (int t = 2; t <= k; ++t) {
CHT Solver;
int ff = t & 1;
for (int i = 1; i < n; ++i) {
if (i >= t) {
ii d = Solver.query(pref[i]);
trace[i][t] = d.second;
dp[ff][i] = d.first + pref[i] * (pref[n] - pref[i]);
}
if (t == k && res < dp[ff][i]) res = max(res, dp[ff][i]), id = i;
// cerr << i << ' ' << t << ' ' << dp[ff][i] << endl;
if (~dp[ff ^ 1][i]) Solver.addLine({pref[i], dp[ff ^ 1][i] - pref[i] * pref[n], i});
}
memset(dp[ff ^ 1], -1, sizeof dp[ff ^ 1]);
}
if (k == 1) {
int t = -1, dd = 0;
for (int i = 1; i <= n; ++i) if (t < dp[1][i])
t = dp[1][i], dd = i;
cout << t << endl << dd << endl;
return 0;
}
cout << res << endl;
vector <int> nn; nn.clear();
for (int i = k; i >= 1; --i) {
nn.push_back(id);
id = trace[id][i];
}
reverse(nn.begin(), nn.end());
for (int v : nn) cout << v << ' ';
return 0;
}
Compilation message
sequence.cpp: In member function 'ii CHT::query(long long int)':
sequence.cpp:39:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (mid != st.size() - 1 && st[mid + 1].val(x) > cur) l = mid + 1;
~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
6 ms |
1916 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
6 ms |
1912 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
5 ms |
1912 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
2040 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
6 ms |
2040 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
7 ms |
2040 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
6 ms |
2040 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Incorrect |
6 ms |
2040 KB |
contestant didn't find the optimal answer: 1005094790 < 1005304678 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
2168 KB |
contestant didn't find the optimal answer: 414012350 < 610590000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
3580 KB |
contestant didn't find the optimal answer: 21499908 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
14 ms |
18040 KB |
contestant didn't find the optimal answer: 1664131784 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
79 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |