QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#841914#9966. High Jumpucup-team1004#AC ✓6ms8300kbC++201.6kb2025-01-04 08:48:572025-01-04 08:48:58

Judging History

你现在查看的是测评时间为 2025-01-04 08:48:58 的历史记录

  • [2025-01-04 13:19:25]
  • 管理员手动重测该提交记录
  • 测评结果:AC
  • 用时:73ms
  • 内存:19664kb
  • [2025-01-04 08:48:58]
  • 评测
  • 测评结果:100
  • 用时:6ms
  • 内存:8300kb
  • [2025-01-04 08:48:57]
  • 提交

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