# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
222160 |
2020-04-12T09:13:27 Z |
VEGAnn |
Akvizna (COCI19_akvizna) |
C++14 |
|
1099 ms |
262144 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 3010;
const ll OO = 1e18;
const ld E = 1e-9;
vector<int> vc;
ld f[N][N];
int n, k;
struct line{
ld k, b;
line(): k(0.0), b(0.0) {}
line(ld _k, ld _b): k(_k), b(_b) {}
};
deque<line> hull;
ld get_cross_point(line fi, line se){
return (fi.b - se.b) / (se.k - fi.k);
}
void insert(line nw){
if (sz(hull) == 0){
hull.PB(nw);
return;
}
while (sz(hull) > 1){
ld pt1 = get_cross_point(nw, hull[1]);
ld pt2 = get_cross_point(hull.back(), hull[0]);
if (pt2 > pt1) break;
hull.pop_front();
}
hull.push_front(nw);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n >> k;
for (int i = 0; i <= k; i++)
for (int j = 0; j <= n; j++)
f[i][j] = -1.0;
f[0][n] = 0.0;
for (int i = 1; i <= k; i++) {
hull.clear();
if (f[i - 1][n] >= -E)
insert({-1.0 / ld(n), f[i - 1][n] + 1.0});
for (int j = n - 1; j >= 0; j--){
if (sz(hull)) {
int l = 0, r = sz(hull) - 1;
while (l < r) {
int md = (l + r + 1) >> 1;
assert(md > 0);
if (get_cross_point(hull[md], hull[md - 1]) + E <= j)
l = md;
else r = md - 1;
}
f[i][j] = hull[l].b + hull[l].k * ld(j);
}
// may be this should be after update f[i][j]
if (f[i - 1][j] >= -E)
insert({-1.0 / ld(j), f[i - 1][j] + 1.0});
}
}
cout << fixed << setprecision(10) << f[k][0];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
768 KB |
Output is correct |
3 |
Correct |
5 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
19792 KB |
Output is correct |
2 |
Correct |
937 ms |
73976 KB |
Output is correct |
3 |
Correct |
962 ms |
105336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
402 ms |
26108 KB |
Output is correct |
2 |
Correct |
848 ms |
64888 KB |
Output is correct |
3 |
Correct |
1020 ms |
114424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
326 ms |
21120 KB |
Output is correct |
2 |
Correct |
584 ms |
46400 KB |
Output is correct |
3 |
Correct |
896 ms |
108640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
408 ms |
27060 KB |
Output is correct |
2 |
Correct |
808 ms |
59640 KB |
Output is correct |
3 |
Correct |
954 ms |
114424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
281 ms |
18176 KB |
Output is correct |
2 |
Correct |
782 ms |
58872 KB |
Output is correct |
3 |
Correct |
896 ms |
97400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
267 ms |
18048 KB |
Output is correct |
2 |
Correct |
1002 ms |
81312 KB |
Output is correct |
3 |
Correct |
1099 ms |
113656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
271 ms |
16640 KB |
Output is correct |
2 |
Correct |
985 ms |
81528 KB |
Output is correct |
3 |
Correct |
1081 ms |
126072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
263 ms |
16768 KB |
Output is correct |
2 |
Correct |
788 ms |
61304 KB |
Output is correct |
3 |
Correct |
1004 ms |
110600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
385 ms |
24192 KB |
Output is correct |
2 |
Correct |
842 ms |
70580 KB |
Output is correct |
3 |
Correct |
1022 ms |
114552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
796 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
796 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
798 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
807 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
809 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
826 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
807 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
776 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
834 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
823 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
826 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
838 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
820 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |