QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#851806 | #9966. High Jump | rgnerdplayer | WA | 1ms | 3992kb | C++23 | 7.8kb | 2025-01-11 00:57:10 | 2025-01-11 00:57:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using Real = long double; // modify these if needed
constexpr Real eps = 1e-9;
template <typename T>
int sign(T x) {
return (x > 0) - (x < 0);
}
int sign(Real x) {
return (x > eps) - (x < -eps);
}
template <typename T>
int cmp(T a, T b) {
return sign(a - b);
}
template <typename T>
struct P {
T x = 0, y = 0;
P(T x = 0, T y = 0) : x(x), y(y) {}
friend istream& operator>>(istream &is, P &p) { return is >> p.x >> p.y; }
friend ostream& operator<<(ostream &os, P p) { return os << p.x << ' ' << p.y; }
friend bool operator==(P a, P b) { return cmp(a.x, b.x) == 0 && cmp(a.y, b.y) == 0; }
friend bool operator!=(P a, P b) { return !(a == b); }
P operator-() { return P(-x, -y); }
P& operator+=(P a) {
x += a.x, y += a.y;
return *this;
}
P& operator-=(P a) {
x -= a.x, y -= a.y;
return *this;
}
P& operator*=(T d) {
x *= d, y *= d;
return *this;
}
P& operator/=(T d) {
x /= d, y /= d;
return *this;
}
friend P operator+(P a, P b) { return P(a) += b; }
friend P operator-(P a, P b) { return P(a) -= b; }
friend P operator*(P a, T d) { return P(a) *= d; }
friend P operator/(P a, T d) { return P(a) /= d; }
friend bool operator<(P a, P b) {
int sx = cmp(a.x, b.x);
return sx != 0 ? sx == -1 : cmp(a.y, b.y) == -1;
}
};
template <typename T>
struct L {
array<P<T>, 2> l;
L(P<T> a = {}, P<T> b = {}) : l{a, b} {}
};
template <typename T>
T dot(P<T> a, P<T> b) { return a.x * b.x + a.y * b.y; }
template <typename T>
T square(P<T> a) { return dot(a, a); }
template <typename T>
T dist2(P<T> a, P<T> b) { return square(a - b); }
template <typename T>
Real length(P<T> a) { return sqrtl(square(a)); }
template <typename T>
Real dist(P<T> a, P<T> b) { return length(a - b); }
template <typename T>
T cross(P<T> a, P<T> b) { return a.x * b.y - a.y * b.x; }
template <typename T>
T cross(P<T> p, P<T> a, P<T> b) { return cross(a - p, b - p); }
template <typename T>
P<Real> normal(P<T> a) {
Real len = length(a);
return P<Real>(a.x / len, a.y / len);
}
template <typename T>
bool up(P<T> a) { return sign(a.y) > 0 || sign(a.y) == 0 && sign(a.x) > 0; }
// 3 colinear? please remember to remove (0, 0)
template <typename T>
bool polar(P<T> a, P<T> b) {
bool ua = up(a), ub = up(b);
return ua != ub ? ua : sign(cross(a, b)) == 1;
}
template <typename T>
bool parallel(P<T> a, P<T> b) {
return sign(cross(a, b)) == 0;
}
template <typename T>
bool sameDirection(P<T> a, P<T> b) {
return sign(cross(a, b)) == 0 && sign(dot(a, b)) == 1;
}
// 1 if on a->b's left
template <typename T>
int side(P<T> p, P<T> a, P<T> b) { return sign(cross(p, a, b)); }
template <typename T>
int side(P<T> p, L<T> l) { return side(p, l.l[0], l.l[1]); }
template <typename T>
P<T> rotate90(P<T> p) {
return {-p.y, p.x};
}
P<Real> rotate(P<Real> p, Real ang) {
return {p.x * cos(ang) - p.y * sin(ang), p.x * sin(ang) + p.y * cos(ang)};
}
template <typename T>
Real angle(P<T> p) {
return atan2(p.y, p.x);
}
template <typename T>
P<T> direction(L<T> l) {
return l.l[1] - l.l[0];
}
template <typename T>
bool parallel(L<T> l1, L<T> l2) {
return sameDirection(direction(l1), direction(l2));
}
template <typename T>
bool sameDirection(L<T> l1, L<T> l2) {
return sameDirection(direction(l1), direction(l2));
}
P<Real> projection(P<Real> p, L<Real> l) {
auto d = direction(l);
return l.l[0] + d * (dot(p - l.l[0], d) / square(d));
}
P<Real> reflection(P<Real> p, L<Real> l) {
return projection(p, l) * 2 - p;
}
template <typename T>
Real pointToLineDist(P<T> p, L<T> l) {
if (l.l[0] == l.l[1]) { return dist(p, l.l[0]); }
return abs(cross(l.l[0] - l.l[1], l.l[0] - p)) / length(direction(l));
}
// better use integers if you don't need exact coordinate
// l <= r is not explicitly required
template <typename T>
P<T> lineIntersection(L<T> l1, L<T> l2) {
return l1.l[0] - direction(l1) * (Real(cross(direction(l2), l1.l[0] - l2.l[0])) / cross(direction(l2), direction(l1)));
}
template <typename T>
bool between(T m, T l, T r) {
return cmp(l, m) == 0 || cmp(m, r) == 0 || l < m != r < m;
}
template <typename T>
bool pointOnSeg(P<T> p, L<T> l) {
return side(p, l) == 0 && between(p.x, l.l[0].x, l.l[1].x) && between(p.y, l.l[0].y, l.l[1].y);
}
template <typename T>
bool pointStrictlyOnSeg(P<T> p, L<T> l) {
return side(p, l) == 0 && sign(dot(p - l.l[0], direction(l))) * sign(dot(p - l.l[1], direction(l))) < 0;
}
template <typename T>
bool overlap(T l1, T r1, T l2, T r2) {
if (l1 > r1) { swap(l1, r1); }
if (l2 > r2) { swap(l2, r2); }
return cmp(r1, l2) != -1 && cmp(r2, l1) != -1;
}
template <typename T>
bool segIntersect(L<T> l1, L<T> l2) {
auto [p1, p2] = l1;
auto [q1, q2] = l2;
return overlap(p1.x, p2.x, q1.x, q2.x) && overlap(p1.y, p2.y, q1.y, q2.y) &&
side(p1, l2) * side(p2, l2) <= 0 &&
side(q1, l1) * side(q2, l1) <= 0;
}
// parallel intersecting is false
template <typename T>
bool segStrictlyIntersect(L<T> l1, L<T> l2) {
auto [p1, p2] = l1;
auto [q1, q2] = l2;
return side(p1, l2) * side(p2, l2) < 0 &&
side(q1, l1) * side(q2, l1) < 0;
}
// parallel or intersect at source doesn't count
template <typename T>
bool rayIntersect(L<T> l1, L<T> l2) {
int x = sign(cross(l1.l[1] - l1.l[0], l2.l[1] - l2.l[0]));
return x == 0 ? false : side(l1.l[0], l2) == x && side(l2.l[0], l1) == -x;
}
template <typename T>
Real pointToSegDist(P<T> p, L<T> l) {
auto d = direction(l);
if (sign(dot(p - l.l[0], d)) >= 0 && sign(dot(p - l.l[1], d)) <= 0) {
return pointToLineDist(p, l);
} else {
return min(dist(p, l.l[0]), dist(p, l.l[1]));
}
}
template <typename T>
Real segDist(L<T> l1, L<T> l2) {
if (segIntersect(l1, l2)) { return 0; }
return min({pointToSegDist(l1.l[0], l2), pointToSegDist(l1.l[1], l2),
pointToSegDist(l2.l[0], l1), pointToSegDist(l2.l[1], l1)});
}
// 2 times area
template <typename T>
T area(vector<P<T>> a) {
T res = 0;
int n = a.size();
for (int i = 0; i < n; i++) {
res += cross(a[i], a[(i + 1) % n]);
}
return res;
}
template <typename T>
bool pointInPoly(P<T> p, vector<P<T>> a) {
int n = a.size(), res = 0;
for (int i = 0; i < n; i++) {
P<T> u = a[i], v = a[(i + 1) % n];
if (pointOnSeg(p, {u, v})) { return true; }
if (cmp(u.y, v.y) <= 0) { swap(u, v); }
if (cmp(p.y, u.y) > 0 || cmp(p.y, v.y) <= 0) { continue; }
res ^= cross(p, u, v) > 0;
}
return res;
}
using Point = P<Real>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n;
cin >> n;
vector<Real> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<Real> dp(n + 1);
// dp[i] = max(dp[j] * a[j] - (a[j] - 1) * i)
dp[n] = n;
deque<Point> h;
for (int i = n; i > 0; i--) {
Point p(a[i] - 1, dp[i] * a[i]);
while (h.size() >= 2 && sign(cross(h.end()[-2] - p, h.back() - p)) >= 0) {
h.pop_back();
}
h.push_back(p);
Point q(1, i - 1);
while (h.size() >= 2 && sign(cross(q, h[1] - h[0])) >= 0) {
h.pop_front();
}
dp[i - 1] = cross(q, h[0]);
}
cout << fixed << setprecision(12);
cout << dp[0] << '\n';
};
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
5 0.9 0.85 0.6 0.456000 0.000000017
output:
2.475200006589
result:
ok found '2.4752000', expected '2.4752000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
1 0.000000001
output:
0.000000001000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2 0.828496829 0.645649353
output:
1.363415270606
result:
ok found '1.3634153', expected '1.3634153', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 0.551197930 0.393255768 0.207104323
output:
0.867956505597
result:
ok found '0.8679565', expected '0.8679565', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
4 0.795361966 0.464795612 0.331129862 0.063526593
output:
1.338829040057
result:
ok found '1.3388290', expected '1.3388290', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
5 0.895888800 0.546833708 0.412641158 0.222811308 0.111288348
output:
1.726785711701
result:
ok found '1.7267857', expected '1.7267857', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
6 0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978
output:
3.825938315957
result:
ok found '3.8259383', expected '3.8259383', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
7 0.964710946 0.660694845 0.569051685 0.519424206 0.347976236 0.103554534 0.003582098
output:
2.660483845894
result:
ok found '2.6604838', expected '2.6604838', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
10 0.908256456 0.813576564 0.742549305 0.649326027 0.554646135 0.461422857 0.372638782 0.277958891 0.183440845 0.094656770
output:
3.465133268121
result:
ok found '3.4651333', expected '3.4651333', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
14 0.965125864 0.957983158 0.894060589 0.767619278 0.708280001 0.562719570 0.524554410 0.428166908 0.332545137 0.257543419 0.171522463 0.080323478 0.048170500 0.020758694
output:
4.986812883512
result:
ok found '4.9868129', expected '4.9868129', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
20 0.999312308 0.993123094 0.792022793 0.785833579 0.773356911 0.773356910 0.760880241 0.710678846 0.707633359 0.706159736 0.706159735 0.705865010 0.705177319 0.680125741 0.655074164 0.604872769 0.604185078 0.403084776 0.402397085 0.000098242
output:
11.722910896183
result:
ok found '11.7229109', expected '11.7229109', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
35 0.999999999 0.500000000 0.333333333 0.250000000 0.200000000 0.166666667 0.142857143 0.125000000 0.111111111 0.100000000 0.090909091 0.083333333 0.076923077 0.071428571 0.066666667 0.062500000 0.058823529 0.055555556 0.052631579 0.050000000 0.047619048 0.045454545 0.043478261 0.041666667 0.0400000...
output:
1.971428584029
result:
ok found '1.9714286', expected '1.9714286', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
42 0.999999997 0.999999957 0.999999558 0.999995984 0.999967570 0.999770574 0.998606056 0.992914780 0.970865633 0.906613334 0.772832688 0.578915971 0.379098588 0.222796093 0.121846038 0.063881487 0.032730211 0.016569178 0.008336477 0.004181321 0.002093945 0.001047795 0.000524103 0.000262103 0.0001310...
output:
11.074111636681
result:
ok found '11.0741116', expected '11.0741116', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
50 0.991131730 0.919779550 0.909523499 0.902541075 0.893803502 0.838347025 0.830500600 0.816318610 0.806306448 0.805684783 0.804210835 0.798232009 0.789231219 0.781205446 0.770460902 0.721836276 0.721271617 0.714886066 0.706142418 0.691410488 0.679542322 0.679399638 0.638774737 0.631666488 0.5962186...
output:
18.746675716668
result:
ok found '18.7466757', expected '18.7466757', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
75 0.720531716 0.718707013 0.709343553 0.694459021 0.689578156 0.682674306 0.679584797 0.678491929 0.670621566 0.666003031 0.665315768 0.659922689 0.659583167 0.658225062 0.658114386 0.653584609 0.649780198 0.639566830 0.636645846 0.630488992 0.628876218 0.628515225 0.615173462 0.613656515 0.6100964...
output:
21.997695508059
result:
ok found '21.9976955', expected '21.9976955', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
99 0.999999999 0.991828371 0.983639875 0.975434302 0.967211435 0.958971054 0.950712932 0.942436838 0.934142534 0.925829777 0.917498319 0.909147903 0.900778269 0.892389147 0.883980263 0.875551333 0.867102067 0.858632167 0.850141328 0.841629234 0.833095563 0.824539982 0.815962149 0.807361713 0.7987383...
output:
35.862420653994
result:
ok found '35.8624207', expected '35.8624207', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
150 0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.99999999 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.99999998 0.999999979 0.999999978 0.999999977 0.999999976 0.99999997...
output:
63.222323372744
result:
ok found '63.2223234', expected '63.2223340', error '0.0000002'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
300 0.999999999 0.707106781 0.577350269 0.500000000 0.447213595 0.408248290 0.377964473 0.353553391 0.333333333 0.316227766 0.301511345 0.288675135 0.277350098 0.267261242 0.258198890 0.250000000 0.242535625 0.235702260 0.229415734 0.223606798 0.218217890 0.213200716 0.208514414 0.204124145 0.200000...
output:
18.262773054737
result:
ok found '18.2627731', expected '18.2627731', error '0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
1000 0.999963957 0.999207697 0.999118706 0.997891974 0.994768087 0.990015892 0.989383451 0.987882675 0.987414725 0.986968311 0.986227809 0.985662929 0.985106306 0.983544346 0.982602847 0.981634680 0.980590743 0.978325691 0.977878867 0.977742455 0.974366243 0.972436723 0.972370267 0.972283135 0.97127...
output:
314.248999866927
result:
ok found '314.2489999', expected '314.2489999', error '0.0000000'
Test #20:
score: -100
Wrong Answer
time: 0ms
memory: 3844kb
input:
1234 0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.99999999 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.99999998 0.999999979 0.999999978 0.999999977 0.999999976 0.9999999...
output:
954.651931272988
result:
wrong answer 1st numbers differ - expected: '954.6635145', found: '954.6519313', error = '0.0000121'