QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352993#3994. Easy JumpJryno1WA 0ms3952kbC++141.5kb2024-03-13 19:31:162024-03-13 19:31:17

Judging History

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

  • [2024-03-13 19:31:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3952kb
  • [2024-03-13 19:31:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
double f[maxn][20][20],g[maxn][20],p[maxn],t1,t2;
double inf=1e9;
int H,S,k;
int n;
bitset<maxn>hav;
int main(){
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);
	cin>>n>>H>>S;
	for(int i=1;i<=n;i++)cin>>p[i],p[i]/=100.0;
	cin>>k;
	for(int i=1;i<=k;i++){
		int pos;
		cin>>pos;
		hav[pos]=1;
	}
	cin>>t1>>t2;
	if(t1>=t2||!S){
		for(int i=n;i>=1;i--){
			g[i][2]=(g[i+2][2]*p[i]+(1-p[i])*t2+1)/p[i];
			for(int j=3;j<=H;j++)g[i][j]=1+p[i]*g[i+1][j]+(1-p[i])*g[i][j-1];
		}
		cout<<setprecision(10)<<g[1][H]<<"\n";
	} else {
		for(int i=n;i>=1;i--){
			if(hav[i]){
				for(int h=2;h<=H;h++)for(int s=0;s<=S;s++)g[h][s]=inf;
				for(int L=2;L<=H;L++){
					f[i][L][S]=(f[i+1][L][S]*p[i]+(1-p[i])*t1+1)/p[i];
					for(int h=L+1;h<=H;h++)f[i][h][S]=1+f[i+1][h][S]*p[i]+(1-p[i])*f[i][h-1][S];
					for(int h=2;h<L;h++)f[i][h][S]=(L-h)*t1+f[i][L][S];
					for(int h=2;h<=H;h++)for(int s=0;s<S;s++)f[i][h][s]=f[i][h][S];
					for(int h=2;h<=H;h++)for(int s=0;s<=S;s++)g[h][s]=min(g[h][s],f[i][h][s]);
				}
				for(int h=2;h<=H;h++)for(int s=0;s<=S;s++)f[i][h][s]=g[h][s];
			} else {
				for(int h=2;h<=H;h++){
					for(int s=0;s<=S;s++){
						if(h==2&&s==0)f[i][h][s]=(f[i+1][h][s]*p[i]+(1-p[i])*t2+1)/p[i];
						else if(h==2)f[i][h][s]=f[i+1][h][s]*p[i]+(1-p[i])*(f[i][h][s-1]+t1)+1;
						else f[i][h][s]=1+p[i]*f[i+1][h][s]+(1-p[i])*f[i][h-1][s];
					}
				}
			}
		}
		cout<<setprecision(10)<<f[1][H][S];
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3952kb

input:

1 2 0
50
0
1 2

output:

4

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

2 3 1
50 50
1 1
1 3

output:

6

result:

ok found '6.0000000', expected '6.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

1 6 4
75
0
64 6

output:

1.341145833

result:

ok found '1.3411458', expected '1.3411458', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

1 5 1
61
1 1
15 43

output:

2.208223197

result:

ok found '2.2082232', expected '2.2082232', error '0.0000000'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3896kb

input:

10 9 3
12 65 76 33 17 20 89 16 4 63
3 2 4 8
73 21

output:

584.0893252

result:

wrong answer 1st numbers differ - expected: '942.4148420', found: '584.0893252', error = '0.3802206'