QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#16910 | #958. Lockout vs tourist | DevilAlex233 | AC ✓ | 243ms | 36676kb | C++20 | 804b | 2021-12-28 18:22:11 | 2022-05-04 12:13:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 22;
typedef double db;
typedef long long ll;
int c[maxn],tot=0;
db a[maxn],b[maxn];
db dp[1<<maxn];
db solve(int n){
db sumder=0,sump=0;
if(a[1]<=b[1])return a[1];
sumder=1./(a[1]-b[1]);
for(int i=2;i<=n;++i){
db deta=a[i-1]-a[i];
db ad=deta*sumder;
if(sump+ad>1)return a[i-1]-(1-sump)/sumder;
if(a[i]<=b[i])return a[i];
sumder+=1./(a[i]-b[i]);
sump+=ad;
}
return a[n]-(1-sump)/sumder;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)scanf("%d",&c[i]);
sort(c,c+n);
for(int i=1;i<(1<<n);++i){
tot=0;
for(int j=n-1;j>=0;--j){
if(!((i>>j)&1))continue;
a[++tot]=c[j];
b[tot]=dp[i^(1<<j)];
}
dp[i]=solve(tot);
}
printf("%.12lf\n",dp[(1<<n)-1]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3864kb
input:
2 6 7
output:
3.230769230769
result:
ok found '3.2307692', expected '3.2307692', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
3 1 1 1
output:
0.833333333333
result:
ok found '0.8333333', expected '0.8333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3780kb
input:
11 1 2 3 4 5 6 7 8 9 10 11
output:
9.442271386610
result:
ok found '9.4422714', expected '9.4422714', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
2 1 1000000000
output:
0.999999999000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
5 76 57 68 36 63
output:
63.353965112431
result:
ok found '63.3539651', expected '63.3539651', error '0.0000000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3776kb
input:
10 550060 445055 787034 728427 572554 894096 875473 622886 575460 119034
output:
818911.373928632820
result:
ok found '818911.3739286', expected '818911.3739286', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4108kb
input:
15 10 8 9 6 9 5 3 9 7 8 7 6 7 10 7
output:
9.498679631760
result:
ok found '9.4986796', expected '9.4986796', error '0.0000000'
Test #8:
score: 0
Accepted
time: 67ms
memory: 12000kb
input:
20 3 2 2 1 2 3 1 3 3 2 1 2 3 2 3 2 3 1 3 1
output:
2.999975198413
result:
ok found '2.9999752', expected '2.9999752', error '0.0000000'
Test #9:
score: 0
Accepted
time: 102ms
memory: 20172kb
input:
21 608646711 538679781 175667175 596079164 43084965 174585378 46825084 647100103 820432909 254925688 469580725 888475497 802835182 554123188 53822453 849477025 715668397 194908968 407987651 349577139 457598738
output:
831669480.282169222832
result:
ok found '831669480.2821692', expected '831669480.2821692', error '0.0000000'
Test #10:
score: 0
Accepted
time: 206ms
memory: 36524kb
input:
22 593316975 268451765 664075355 817013319 325389147 553878522 663160635 289932897 995002446 771863307 252061346 171723220 102306933 722521207 52895206 996540774 335816175 415049181 629862034 371890996 327908946 357122932
output:
899795716.348148584366
result:
ok found '899795716.3481486', expected '899795716.3481486', error '0.0000000'
Test #11:
score: 0
Accepted
time: 180ms
memory: 36624kb
input:
22 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152
output:
895851.534057118930
result:
ok found '895851.5340571', expected '895851.5340571', error '0.0000000'
Test #12:
score: 0
Accepted
time: 226ms
memory: 36612kb
input:
22 1000001 1000002 1000003 1000004 1000005 1000006 1000007 1000008 1000009 1000010 1000011 1000012 1000013 1000014 1000015 1000016 1000017 1000018 1000019 1000020 1000021 1000022
output:
1000020.442125287838
result:
ok found '1000020.4421253', expected '1000020.4421253', error '0.0000000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
output:
999999724.426807761192
result:
ok found '999999724.4268078', expected '999999724.4268078', error '0.0000000'
Test #14:
score: 0
Accepted
time: 243ms
memory: 36676kb
input:
22 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 102ms
memory: 20148kb
input:
21 728645832 499372030 251249515 630474794 602042850 686098859 164334367 88772048 746898743 759695983 264178590 77784010 969248695 194487863 333341710 979132664 389787588 237190234 881432878 265149252 412117176
output:
904983051.313902497292
result:
ok found '904983051.3139025', expected '904983051.3139025', error '0.0000000'
Test #16:
score: 0
Accepted
time: 207ms
memory: 36612kb
input:
22 314176712 731128902 493616429 895194945 944147610 264333375 726725941 275896968 22590087 347618504 348534546 434375739 41042380 833655175 812796321 965972943 895005482 106474689 268333939 73317639 692105187 921714965
output:
931516498.441391706467
result:
ok found '931516498.4413917', expected '931516498.4413917', error '0.0000000'
Test #17:
score: 0
Accepted
time: 205ms
memory: 36676kb
input:
22 619182033 404890231 483695686 505942949 17974691 191865554 285191465 20725875 768798333 549358594 794203186 500489670 673327262 914017660 189568084 691193705 497008772 813277003 87684441 894142475 811860050 857365145
output:
872232180.526017546654
result:
ok found '872232180.5260175', expected '872232180.5260175', error '0.0000000'
Test #18:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
1 1
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'