QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33197 | #958. Lockout vs tourist | Wu_Ren | WA | 2ms | 3896kb | C++17 | 670b | 2022-05-29 21:04:15 | 2022-05-29 21:04:18 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
using namespace std;
int n,m,c[22];
ld f[4194304],b[22],a[22];
ld calc(){
ld K=0,B=0;
for(int i=0;i<m;i++) if(b[i]<a[i]) K+=1/(b[i]-a[i]),B+=-a[i]/(b[i]-a[i]);
for(int i=0;i<m;i++){
if(K*a[i]+B<=1) return (1-B)/K;
if(b[i]<a[i]) K-=1/(b[i]-a[i]),B-=-a[i]/(b[i]-a[i]);
}
return (1-B)/K;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&c[i]);
sort(a,a+n);
for(int S=1;S<(1<<n);S++){
m=0;
for(int i=0;i<n;i++) if((S>>i)&1){
b[m]=f[S^(1<<i)],a[m++]=c[i];
if(b[m-1]>=a[m-1]) f[S]=max(f[S],a[m-1]);
}
f[S]=max(f[S],calc());
}
printf("%.18Lf",f[(1<<n)-1]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3896kb
input:
2 6 7
output:
3.230769230769230769
result:
ok found '3.2307692', expected '3.2307692', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3832kb
input:
3 1 1 1
output:
0.833333333333333333
result:
ok found '0.8333333', expected '0.8333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
11 1 2 3 4 5 6 7 8 9 10 11
output:
9.442271386610331755
result:
ok found '9.4422714', expected '9.4422714', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
2 1 1000000000
output:
0.999999999000000001
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3740kb
input:
5 76 57 68 36 63
output:
62.816143569032191551
result:
wrong answer 1st numbers differ - expected: '63.3539651', found: '62.8161436', error = '0.0084892'