QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#842690 | #9966. High Jump | ucup-team3474# | WA | 38ms | 6756kb | C++23 | 3.5kb | 2025-01-04 14:07:19 | 2025-01-04 14:07:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std ;
#define vec point
typedef double db;
const db eps = 1e-6;
const db pi = acos(-1.0);
const db inf = 40000;
int sgn(db x) {
if (x < -eps)
return -1;
else if (x > eps)
return 1;
else
return 0;
}
int cmp(db x, db y) { return sgn(x - y); }
void print(int num, db x) { cout << fixed << setprecision(num) << x << '\n'; }
struct point {
db x, y;
point() {}
point(db x2, db y2) { x = x2, y = y2; }
void input() {
int x2, y2;
cin >> x2 >> y2;
x = x2;
y = y2;
}
point operator+(const point &s) const { return (point){x + s.x, y + s.y}; }
point operator-(const point &s) const { return (point){x - s.x, y - s.y}; }
point operator*(const db &k) const { return (point){x * k, y * k}; }
point operator/(const db &k) const { return (point){x / k, y / k}; }
db operator*(const point &a) const { return x * a.x + y * a.y; }
db operator^(const point &a) const { return x * a.y - y * a.x; }
bool operator<(point b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
bool equal(point p2) { return cmp(x, p2.x) == 0 && cmp(y, p2.y) == 0; }
db get_angle() { return atan2(y, x); }
int getP() const { return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1); }
db sq(db x) { return x * x; }
db dis(point p) { return sqrtl(sq(x - p.x) + sq(y - p.y)); }
db len() { return sqrtl(sq(x) + sq(y)); }
db len2() { return sq(x) + sq(y); }
point unit() {
db w = len();
return (point){x / w, y / w};
}
vec rotate_left() { return vec(-y, x); }
vec rotate_right() { return vec(y, -x); }
point move(db r) {
db l = len();
if (sgn(l) == 0)
return *this;
else
return point(x * r / l, y * r / l);
}
vec rotate(db ang) { return vec({x * cos(ang) - y * sin(ang), y * cos(ang) + x * sin(ang)}); }
};
db cross(vec s, vec t) { return s.x * t.y - s.y * t.x; }
db dot(vec s, vec t) { return s.x * t.x + s.y * t.y; }
void solve()
{
int n ;
cin >> n ;
vector<db> p(n) ;
for(int i = 0 ; i < n ; i ++) cin >> p[i] ;
// dp[i] = \max val[i] * lose[j] + win[i] * dp[j]
vector<db> dp(n) ;
dp[n - 1] = p[n - 1] * n ;
vector<vec> v ;
auto add = [&](int id)
{
db x = 1.0 - p[id] ;
db y = dp[id] ;
vec v3 = {x , y} ;
while(v.size() >= 2)
{
vec v2 = v.back() ; v.pop_back() ;
vec v1 = v.back() ;
if(sgn(cross(v2 - v1 , v3 - v2)) >= 0)
{
v.push_back(v2) ;
break ;
}
}
v.push_back(v3) ;
} ;
add(n - 1) ;
for(int i = n - 2 ; i >= 0 ; i --)
{
vec now = {p[i] * (i + 1) , p[i]} ;
int l = 0 , r = v.size() - 1 ;
auto cal = [&](int id)
{
return dot(v[id] , now) ;
} ;
while(r - l >= 5)
{
db lmid = (2 * l + r) / 3 ;
db rmid = (2 * r + l + 2) / 3 ;
if(cal(lmid) >= cal(rmid)) r = rmid - 1 ;
else l = lmid + 1 ;
}
for(int j = l ; j <= r ; j ++) dp[i] = max(dp[i] , dot(now , v[j])) ;
add(i) ;
}
cout << fixed << setprecision(12) << *max_element(dp.begin() , dp.end()) << '\n' ;
}
int main()
{
std::ios::sync_with_stdio(false) , cin.tie(0) ;
int T = 1 ;
while (T --) solve() ;
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
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: 3780kb
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: 4000kb
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: 4016kb
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: 3896kb
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: 3780kb
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: 4004kb
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: 3908kb
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: 3884kb
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: 3720kb
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: 3872kb
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: 3712kb
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.971428577633
result:
ok found '1.9714286', expected '1.9714286', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
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: 4004kb
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: 3780kb
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: 3876kb
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: 3908kb
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.222334038287
result:
ok found '63.2223340', expected '63.2223340', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4032kb
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: 3852kb
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: 0
Accepted
time: 1ms
memory: 3952kb
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.663514488509
result:
ok found '954.6635145', expected '954.6635145', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
3000 0.999479046 0.999467644 0.999384041 0.998543297 0.998530995 0.998473219 0.998371918 0.997799207 0.997737486 0.996491143 0.996240960 0.995286006 0.994641002 0.994623139 0.994477752 0.994465945 0.994343783 0.993985630 0.993841254 0.993633501 0.993625451 0.993495246 0.993371638 0.993313042 0.99251...
output:
934.613452337382
result:
ok found '934.6134523', expected '934.6134523', error '0.0000000'
Test #22:
score: 0
Accepted
time: 4ms
memory: 4196kb
input:
10000 0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.999999990 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.999999980 0.999999979 0.999999978 0.954488188 0.876604603 0.8078...
output:
29.189038043790
result:
ok found '29.1890380', expected '29.1890380', error '0.0000000'
Test #23:
score: 0
Accepted
time: 7ms
memory: 3788kb
input:
23555 0.999818911 0.999779383 0.999771707 0.999753903 0.999742135 0.999733246 0.999717661 0.999712926 0.999652283 0.999647616 0.999638618 0.999560822 0.999556789 0.999499466 0.999489721 0.999475268 0.999454593 0.999447586 0.999438520 0.999435065 0.999417583 0.999402401 0.999400167 0.999400098 0.9993...
output:
7396.227922190849
result:
ok found '7396.2279222', expected '7396.2279222', error '0.0000000'
Test #24:
score: 0
Accepted
time: 11ms
memory: 3856kb
input:
33333 0.999998516 0.999989382 0.999956277 0.999903321 0.999893982 0.999885155 0.999833175 0.999817408 0.999814615 0.999766219 0.999763276 0.999699760 0.999670993 0.999640968 0.999610071 0.999573638 0.999566420 0.999482175 0.999434538 0.999420310 0.999389080 0.999376248 0.999369994 0.999368427 0.9993...
output:
10263.199349936343
result:
ok found '10263.1993499', expected '10263.1993499', error '0.0000000'
Test #25:
score: 0
Accepted
time: 36ms
memory: 6756kb
input:
90875 0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.999999990 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.999999980 0.999999979 0.999999978 0.999999977 0.999999976 0.9999...
output:
89310.244826015114
result:
ok found '89310.2448260', expected '89310.2448260', error '0.0000000'
Test #26:
score: -100
Wrong Answer
time: 38ms
memory: 5580kb
input:
100000 0.999988194 0.999982288 0.999970500 0.999958782 0.999946973 0.999935185 0.999929279 0.999917653 0.999907318 0.999901412 0.999889647 0.999889646 0.999878573 0.999866855 0.999860949 0.999849161 0.999849160 0.999837533 0.999837532 0.999825733 0.999814014 0.999808108 0.999797773 0.999785968 0.999...
output:
30691.079303763010
result:
wrong answer 1st numbers differ - expected: '30691.8126127', found: '30691.0793038', error = '0.0000239'