QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841900 | #9966. High Jump | ucup-team1004# | WA | 1ms | 8164kb | C++20 | 1.6kb | 2025-01-04 08:44:01 | 2025-01-04 08:44:02 |
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 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'