QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841914 | #9966. High Jump | ucup-team1004# | AC ✓ | 6ms | 8300kb | C++20 | 1.6kb | 2025-01-04 08:48:57 | 2025-01-04 08:48:58 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e5+5,M=(1<<8)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n;
db p[N],dp[N];
using cp=complex<db>;
db slope(cp x,cp y){return (x.imag()-y.imag())*1.0/(x.real()-y.real());}
cp Q[N];int H,T;
void Solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
dp[n]=n;H=1;T=0;
for(int i=n-1;~i;i--){
cp w=cp(p[i+1],p[i+1]*dp[i+1]);
while(H<T&&slope(Q[T-1],Q[T])<slope(Q[T],w)) T--;
Q[++T]=w;
while(H<T&&slope(Q[H],Q[H+1])>i) H++;
dp[i]=i-i*Q[H].real()+Q[H].imag();
// for(int j=i+1;j<=n;j++) dp[i]=max(dp[i],(1-p[j])*i+p[j]*dp[j]);
}
printf("%.10lf\n",dp[0]);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8144kb
input:
5 0.9 0.85 0.6 0.456000 0.000000017
output:
2.4752000066
result:
ok found '2.4752000', expected '2.4752000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8132kb
input:
1 0.000000001
output:
0.0000000010
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 8132kb
input:
2 0.828496829 0.645649353
output:
1.3634152706
result:
ok found '1.3634153', expected '1.3634153', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 8136kb
input:
3 0.551197930 0.393255768 0.207104323
output:
0.8679565056
result:
ok found '0.8679565', expected '0.8679565', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 8088kb
input:
4 0.795361966 0.464795612 0.331129862 0.063526593
output:
1.3388290401
result:
ok found '1.3388290', expected '1.3388290', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 8140kb
input:
5 0.895888800 0.546833708 0.412641158 0.222811308 0.111288348
output:
1.7267857117
result:
ok found '1.7267857', expected '1.7267857', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 8144kb
input:
6 0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978
output:
3.8259383160
result:
ok found '3.8259383', expected '3.8259383', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 8128kb
input:
7 0.964710946 0.660694845 0.569051685 0.519424206 0.347976236 0.103554534 0.003582098
output:
2.6604838459
result:
ok found '2.6604838', expected '2.6604838', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 8156kb
input:
10 0.908256456 0.813576564 0.742549305 0.649326027 0.554646135 0.461422857 0.372638782 0.277958891 0.183440845 0.094656770
output:
3.4651332681
result:
ok found '3.4651333', expected '3.4651333', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 8000kb
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.9868128835
result:
ok found '4.9868129', expected '4.9868129', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 8128kb
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.7229108962
result:
ok found '11.7229109', expected '11.7229109', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 8148kb
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.9714285841
result:
ok found '1.9714286', expected '1.9714286', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 8088kb
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.0741116367
result:
ok found '11.0741116', expected '11.0741116', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 8148kb
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.7466757167
result:
ok found '18.7466757', expected '18.7466757', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 8064kb
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.9976955081
result:
ok found '21.9976955', expected '21.9976955', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 8092kb
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.8624206540
result:
ok found '35.8624207', expected '35.8624207', error '0.0000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 8128kb
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.2223340383
result:
ok found '63.2223340', expected '63.2223340', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 8092kb
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.2627730547
result:
ok found '18.2627731', expected '18.2627731', error '0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 8148kb
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.2489998669
result:
ok found '314.2489999', expected '314.2489999', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 8032kb
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.6635144885
result:
ok found '954.6635145', expected '954.6635145', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 8128kb
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.6134523374
result:
ok found '934.6134523', expected '934.6134523', error '0.0000000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 8172kb
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.1890380438
result:
ok found '29.1890380', expected '29.1890380', error '0.0000000'
Test #23:
score: 0
Accepted
time: 5ms
memory: 8004kb
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.2279221909
result:
ok found '7396.2279222', expected '7396.2279222', error '0.0000000'
Test #24:
score: 0
Accepted
time: 6ms
memory: 8144kb
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.1993499363
result:
ok found '10263.1993499', expected '10263.1993499', error '0.0000000'
Test #25:
score: 0
Accepted
time: 3ms
memory: 8300kb
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.2448260151
result:
ok found '89310.2448260', expected '89310.2448260', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed