# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282603 |
2020-08-24T15:30:37 Z |
cgiosy |
Akvizna (COCI19_akvizna) |
C++17 |
|
1329 ms |
2608 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using flt=double;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, K;
cin>>N>>K;
flt l=0, r=1+1e-12;
vector<int> C(N+1), P(N+1);
cout<<fixed<<setprecision(9);
auto f=[&](flt m) {
vector<double> D(N+1);
vector<int> T(1<<32-__builtin_clz(N));
auto f=[&](int j, int i) {
return D[j]+flt(i-j)/i;
};
auto cmp=[&](int i, int j, int x) {
return f(i, x)>f(j, x);
};
auto add=[&](int a) {
int s=1, e=N, i=1;
while(i) {
int m=s+e>>1, &b=T[i];
if(cmp(a, b, m)) swap(a, b);
if(cmp(a, b, s)) e=m-1, i=i*2;
else if(cmp(a, b, e)) s=m+1, i=i*2+1;
else break;
}
};
auto get=[&](int x) {
int s=1, e=N, i=1, a=0;
while(i) {
int m=s+e>>1, b=T[i];
if(cmp(b, a, x)) a=b;
if(x<m) e=m-1, i=i*2;
else if(x>m) s=m+1, i=i*2+1;
else break;
}
return a;
};
D[0]=0;
for(int i=1; i<=N; i++) {
add(i-1);
int p=get(i);
P[i]=p;
C[i]=C[p]+1;
D[i]=f(p, i)-m;
}
return make_pair(C[N], D[N]+K*m);
};
while(r-l>1e-12) {
flt m=(l+r)/2;
auto[k,x]=f(m);
if(k<K) r=m;
else if(k>K) l=m;
else { l=r=m; break; }
}
cout<<fixed<<setprecision(9)<<f((l+r)/2).second;
}
Compilation message
akvizna.cpp: In lambda function:
akvizna.cpp:15:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
15 | vector<int> T(1<<32-__builtin_clz(N));
| ~~^~~~~~~~~~~~~~~~~
akvizna.cpp: In lambda function:
akvizna.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int m=s+e>>1, &b=T[i];
| ~^~
akvizna.cpp: In lambda function:
akvizna.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m=s+e>>1, b=T[i];
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
384 KB |
Output is correct |
2 |
Correct |
23 ms |
440 KB |
Output is correct |
3 |
Correct |
20 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
384 KB |
Output is correct |
2 |
Correct |
17 ms |
384 KB |
Output is correct |
3 |
Correct |
21 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
384 KB |
Output is correct |
2 |
Correct |
16 ms |
384 KB |
Output is correct |
3 |
Correct |
20 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
512 KB |
Output is correct |
2 |
Correct |
20 ms |
384 KB |
Output is correct |
3 |
Correct |
21 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
384 KB |
Output is correct |
2 |
Correct |
20 ms |
384 KB |
Output is correct |
3 |
Correct |
20 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
384 KB |
Output is correct |
2 |
Correct |
22 ms |
384 KB |
Output is correct |
3 |
Correct |
22 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
384 KB |
Output is correct |
2 |
Correct |
20 ms |
384 KB |
Output is correct |
3 |
Correct |
22 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
384 KB |
Output is correct |
2 |
Correct |
17 ms |
384 KB |
Output is correct |
3 |
Correct |
21 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
436 KB |
Output is correct |
2 |
Correct |
20 ms |
436 KB |
Output is correct |
3 |
Correct |
21 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1117 ms |
2452 KB |
Output is correct |
2 |
Correct |
1222 ms |
2396 KB |
Output is correct |
3 |
Correct |
1158 ms |
2352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1132 ms |
2376 KB |
Output is correct |
2 |
Correct |
1243 ms |
2556 KB |
Output is correct |
3 |
Correct |
1222 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1092 ms |
2436 KB |
Output is correct |
2 |
Correct |
1285 ms |
2532 KB |
Output is correct |
3 |
Correct |
1259 ms |
2540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1188 ms |
2408 KB |
Output is correct |
2 |
Correct |
1255 ms |
2552 KB |
Output is correct |
3 |
Correct |
1215 ms |
2372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1068 ms |
2336 KB |
Output is correct |
2 |
Correct |
1268 ms |
2432 KB |
Output is correct |
3 |
Correct |
1198 ms |
2448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1282 ms |
2608 KB |
Output is correct |
2 |
Correct |
1225 ms |
2440 KB |
Output is correct |
3 |
Correct |
1209 ms |
2452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1186 ms |
2432 KB |
Output is correct |
2 |
Correct |
1180 ms |
2352 KB |
Output is correct |
3 |
Correct |
1184 ms |
2344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1071 ms |
2376 KB |
Output is correct |
2 |
Correct |
1329 ms |
2464 KB |
Output is correct |
3 |
Correct |
1182 ms |
2468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1143 ms |
2540 KB |
Output is correct |
2 |
Correct |
1252 ms |
2432 KB |
Output is correct |
3 |
Correct |
1278 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1166 ms |
2540 KB |
Output is correct |
2 |
Correct |
1233 ms |
2444 KB |
Output is correct |
3 |
Correct |
1279 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1174 ms |
2532 KB |
Output is correct |
2 |
Correct |
1292 ms |
2472 KB |
Output is correct |
3 |
Correct |
1289 ms |
2528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1074 ms |
2532 KB |
Output is correct |
2 |
Correct |
1296 ms |
2532 KB |
Output is correct |
3 |
Correct |
1289 ms |
2528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1241 ms |
2536 KB |
Output is correct |
2 |
Correct |
1275 ms |
2528 KB |
Output is correct |
3 |
Correct |
1303 ms |
2476 KB |
Output is correct |