#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
struct Func{
int p;
double q;
Func(){}
Func(int _p, double _q): p(_p), q(_q) {}
double operator()(int x) const{
return pow(x-p, (double)k/2) + q;
}
};
int cross(const Func &f, const Func &g){
int l = g.p + 1, r = n, ans = n+1;
while(l<=r){
int mid = (l+r)>>1;
if (f(mid) >= g(mid)) ans = mid, r = mid-1;
else l = mid+1;
}
return ans;
}
struct Hull{
vector<Func> st;
void insert(Func g){
// printf("insert %d %f\n", g.p, g.q);
while(st.size() >= 2){
if (cross(*++st.rbegin(), st.back()) > cross(st.back(), g)) break;
st.pop_back();
}
st.push_back(g);
}
double query(int x){
int l = 0, r = (int)st.size()-2, ans = (int)st.size()-1;
while(l<=r){
int mid = (l+r)>>1;
if (st[mid](x) >= st[mid+1](x)) ans = mid, r = mid-1;
else l = mid+1;
}
// for (int i=0;i<(int)st.size();i++) printf("%f ", st[i](x));
// printf("\n");
// printf("return: %f \n", st[ans](x));
return st[ans](x);
}
}H[1001000];
int a[1001000], idx[1001000];
vector<int> V[1001000];
double dp[1001000];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
ll S = 0;
for (int i=1;i<=n;i++){
cin >> a[i];
V[a[i]].push_back(i);
idx[i] = (int)V[a[i]].size()-1;
S += a[i];
}
if (k==2){
printf("%.15f\n", (double)S);
return 0;
}
for (int i=1;i<=n;i++){
// printf(" ok %d %f\n", idx[i]-1, dp[i-1]);
H[a[i]].insert(Func(idx[i]-1, dp[i-1]));
dp[i] = H[a[i]].query(idx[i]);
// printf("%d -> %.15f\n", i, dp[i]);
}
printf("%.15f\n", dp[n]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
24 ms |
47260 KB |
Output is correct |
3 |
Correct |
24 ms |
47316 KB |
Output is correct |
4 |
Correct |
23 ms |
47316 KB |
Output is correct |
5 |
Incorrect |
23 ms |
47316 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
47344 KB |
Output is correct |
2 |
Incorrect |
21 ms |
47352 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
47344 KB |
Output is correct |
2 |
Incorrect |
21 ms |
47352 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
47344 KB |
Output is correct |
2 |
Incorrect |
21 ms |
47352 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2445 ms |
69248 KB |
Output is correct |
2 |
Correct |
2547 ms |
71688 KB |
Output is correct |
3 |
Correct |
999 ms |
58276 KB |
Output is correct |
4 |
Correct |
1654 ms |
60040 KB |
Output is correct |
5 |
Correct |
1239 ms |
100688 KB |
Output is correct |
6 |
Correct |
1508 ms |
102700 KB |
Output is correct |
7 |
Correct |
1505 ms |
102728 KB |
Output is correct |
8 |
Correct |
1459 ms |
102772 KB |
Output is correct |
9 |
Correct |
1469 ms |
102800 KB |
Output is correct |
10 |
Correct |
1509 ms |
102732 KB |
Output is correct |
11 |
Correct |
2364 ms |
71064 KB |
Output is correct |
12 |
Correct |
2344 ms |
70732 KB |
Output is correct |
13 |
Correct |
2096 ms |
68952 KB |
Output is correct |
14 |
Correct |
3031 ms |
72416 KB |
Output is correct |
15 |
Correct |
2913 ms |
74720 KB |
Output is correct |
16 |
Correct |
2997 ms |
73020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
24 ms |
47260 KB |
Output is correct |
3 |
Correct |
24 ms |
47316 KB |
Output is correct |
4 |
Correct |
23 ms |
47316 KB |
Output is correct |
5 |
Incorrect |
23 ms |
47316 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |