#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef long double ld;
const int maxn = 1e5+5, maxk = 205;
int N, K, a[maxn];
ll pre[maxn];
ll dp[maxn][maxk];
int previous[maxn][maxk];
struct FN
{
int id;
ll m, b; //in this case, function is a line
FN(ll _m, ll _b, int _id) : m(_m), b(_b), id(_id) {}
ll eval(ll x) const {
return m*x + b;
}
ld intersect(const FN& r) const { //returns x coordinate of intersection
//assert(m != r.m);
return (ld)(r.b-b)/(ld)(m-r.m);
}
friend bool comp(const FN& l1, const FN& l2, const FN& l) {
//order in deque: l1, l2, l
//true --> l2 is unnecessary
ld x1 = l1.intersect(l);
ld x2 = l1.intersect(l2);
return x1 <= x2;
}
};
struct Hull: public deque<FN> //convex hull for maximum
{
void add(const FN& l) {
//slopes coming in -1,-2,-3,...so add to front of deque rather than back (querying for maximum)
//if adding to back, need to change the indices
while (size() >= 2 &&
comp(*prev(rbegin()),*rbegin(),l)) {
pop_back();
}
push_front(l);
}
pair<ll,int> query(ll x) {
while (size() >= 2 && begin()->eval(x) <= next(begin())->eval(x)) {
pop_front();
}
return {begin()->eval(x),begin()->id};
}
} hulls[maxk];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> a[i];
pre[i] = a[i] + pre[i-1];
}
for (int i = 2; i <= N; i++) {
for (int k = 1; k <= K; k++) {
if (pre[i-1] > pre[i-2] ||
(pre[i-1] == pre[i-2] &&
dp[i-1][k-1]-pre[i-1]*pre[i-1] >
dp[i-2][k-1]-pre[i-2]*pre[i-2])) {
hulls[k-1].add(FN(pre[i-1],dp[i-1][k-1]-pre[i-1]*pre[i-1],i-1));
}
auto p = hulls[k-1].query(pre[i]);
dp[i][k] = p.first;
previous[i][k] = p.second;
//printf("[%d][%d]: %d\n",i,k,dp[i][k]);
}
}
//output
cout << dp[N][K] << '\n';
int curr = N;
int k = K;
vector<int> ans;
while (k > 0) {
curr = previous[curr][k];
k--;
ans.push_back(curr);
}
reverse(ans.begin(),ans.end());
for (int i: ans) {
cout << i << ' ';
}
cout << '\n';
}
Compilation message
sequence.cpp: In constructor 'FN::FN(ll, ll, int)':
sequence.cpp:15:11: warning: 'FN::b' will be initialized after [-Wreorder]
ll m, b; //in this case, function is a line
^
sequence.cpp:14:9: warning: 'int FN::id' [-Wreorder]
int id;
^~
sequence.cpp:16:5: warning: when initialized here [-Wreorder]
FN(ll _m, ll _b, int _id) : m(_m), b(_b), id(_id) {}
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
508 KB |
contestant didn't find the optimal answer: 106 < 108 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
632 KB |
contestant didn't find the optimal answer: 1092528 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
888 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
2 ms |
888 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
4 ms |
1656 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Incorrect |
3 ms |
1016 KB |
contestant didn't find the optimal answer: 211605090300 < 1499437552673 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
2936 KB |
contestant didn't find the optimal answer: 347830 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
21 ms |
24696 KB |
contestant didn't find the optimal answer: 1694250000 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
118 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |