# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
222183 |
2020-04-12T09:45:00 Z |
VEGAnn |
Akvizna (COCI19_akvizna) |
C++14 |
|
1500 ms |
51136 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 = 100100;
const ll OO = 1e18;
const ld E = 1e-9;
vector<int> vc;
pair<ld, int> f[N];
int n, k;
struct line{
ld k, b;
int bl;
line(): k(0.0), b(0.0), bl(0) {}
line(ld _k, ld _b, int i): k(_k), b(_b), bl(i) {}
};
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);
}
bool check(ld extra){
fill(f, f + n + 1, MP(-1.0, 0));
f[n] = MP(0.0, 0);
insert({-1.0 / ld(n), f[n].ft + 1.0, 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[j] = MP(hull[l].b + hull[l].k * ld(j) + extra, hull[l].bl + 1);
}
// may be this should be after update f[i][j]
if (f[j].ft >= -E)
insert({-1.0 / ld(j), f[j].ft + 1.0, f[j].sd});
}
return (f[0].sd <= k);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n >> k;
ld l = 0, r = ld(1e10);
check(0);
if (f[0].sd != k) {
for (int it = 0; it < 100; it++){
ld md = (l + r) / 2.0;
if (check(-md))
r = md;
else l = md;
if (f[0].sd == k){
l = md;
break;
}
}
}
check(-l);
cout << fixed << setprecision(10) << f[0].ft + l * ld(k);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
100 ms |
4064 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
117 ms |
3532 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
107 ms |
4088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
107 ms |
4088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
103 ms |
4088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
94 ms |
3932 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
110 ms |
4088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
99 ms |
3576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
113 ms |
4216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1591 ms |
36452 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1594 ms |
51136 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1565 ms |
43572 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1602 ms |
43472 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1596 ms |
48444 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1595 ms |
42944 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1594 ms |
45616 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1599 ms |
40900 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1595 ms |
42324 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1599 ms |
44716 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1585 ms |
45972 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1597 ms |
46624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1579 ms |
45652 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |