QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#841900#9966. High Jumpucup-team1004#WA 1ms8164kbC++201.6kb2025-01-04 08:44:012025-01-04 08:44:02

Judging History

你现在查看的是最新测评结果

  • [2025-01-04 08:44:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8164kb
  • [2025-01-04 08:44:01]
  • 提交

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 st[N];int sh;
void Solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
	dp[n]=n;
	for(int i=n-1;~i;i--){
		cp w=cp(p[i+1],p[i+1]*dp[i+1]);
		while(sh>1&&slope(st[sh-1],st[sh])<slope(st[sh],w)) sh--;
		st[++sh]=w;
		while(sh>1&&slope(st[sh-1],st[sh])<i) sh--;
		dp[i]=i-i*st[sh].real()+st[sh].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: 0ms
memory: 8124kb

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: 8072kb

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: 8116kb

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: 8164kb

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: 8064kb

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: 0ms
memory: 8120kb

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: 8124kb

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: -100
Wrong Answer
time: 0ms
memory: 8120kb

input:

7
0.964710946 0.660694845 0.569051685 0.519424206 0.347976236 0.103554534 0.003582098

output:

2.3423842983

result:

wrong answer 1st numbers differ - expected: '2.6604838', found: '2.3423843', error = '0.1195645'