ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202973 | #2451. A | hegm | 100 | 1731ms | 9388kb | C++11 | 818b | 2024-02-18 09:45:10 | 2024-02-18 13:22:37 |
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define make make_pair
#define N 21
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,l[N],w[N];
double f[1<<N];
signed main()
{
n=read();
for(int i=0;i<n;i++)l[i]=read();
for(int i=0;i<n;i++)w[i]=read();
f[0]=0;int lim=(1<<n)-1;
for(int i=0;i<=lim;i++)
{
int sum=0;
for(int j=0;j<n;j++)if(i&(1<<j))sum+=w[j];
for(int j=0;j<n;j++)
{
if(i&(1<<j))continue;
double k=w[j]*l[j]*1.0/(2.0*(sum+w[j]));
f[i|(1<<j)]=max(f[i|(1<<j)],f[i]+k);
f[i|(1<<j)]=max(f[i|(1<<j)],l[j]*1.0-k);
}
}
printf("%.10f",f[lim]);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 1196kb
input:
3 390 119 245 181 46 146
output:
295.3753351206
result:
ok found '295.375335121', expected '295.375335121', error '0.000000000'
Test #2:
score: 5
Accepted
time: 0ms
memory: 1196kb
input:
3 393 100 110 245 361 73
output:
322.0979381443
result:
ok found '322.097938144', expected '322.097938144', error '0.000000000'
Test #3:
score: 5
Accepted
time: 0ms
memory: 1192kb
input:
3 397 848 206 540 675 1000
output:
725.5271048819
result:
ok found '725.527104882', expected '725.527104882', error '0.000000000'
Test #4:
score: 5
Accepted
time: 0ms
memory: 1192kb
input:
3 400 596 70 835 222 158
output:
559.3538228287
result:
ok found '559.353822829', expected '559.353822829', error '0.000000000'
Test #5:
score: 5
Accepted
time: 0ms
memory: 1196kb
input:
6 403 577 166 131 536 85 998 700 669 172 530 862
output:
613.2118074418
result:
ok found '613.211807442', expected '613.211807442', error '0.000000000'
Test #6:
score: 5
Accepted
time: 0ms
memory: 1196kb
input:
6 406 325 30 194 851 12 111 773 412 24 382 906
output:
817.3342307759
result:
ok found '817.334230776', expected '817.334230776', error '0.000000000'
Test #7:
score: 5
Accepted
time: 0ms
memory: 1196kb
input:
6 410 74 126 489 165 938 223 846 156 876 234 950
output:
818.3569917172
result:
ok found '818.356991717', expected '818.356991717', error '0.000000000'
Test #8:
score: 5
Accepted
time: 0ms
memory: 1196kb
input:
6 413 54 991 785 712 865 336 918 668 728 86 994
output:
1259.8145048214
result:
ok found '1259.814504821', expected '1259.814504821', error '0.000000000'
Test #9:
score: 5
Accepted
time: 150ms
memory: 9380kb
input:
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 416 803 87 80 27 792 680 991 411 348 938 38 354 752 883 2...
output:
2.8940772994
result:
ok found '2.894077299', expected '2.894077299', error '0.000000000'
Test #10:
score: 5
Accepted
time: 146ms
memory: 9376kb
input:
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 419 551 183 143 341 719 793 832 923 200 790 82 724 298 30...
output:
2.9022242463
result:
ok found '2.902224246', expected '2.902224246', error '0.000000000'
Test #11:
score: 5
Accepted
time: 131ms
memory: 9380kb
input:
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 423 531 47 439 888 645 905 905 666 52 642 126 863 76 499 ...
output:
3.1520126440
result:
ok found '3.152012644', expected '3.152012644', error '0.000000000'
Test #12:
score: 5
Accepted
time: 146ms
memory: 9380kb
input:
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 426 280 143 734 202 572 17 977 178 904 494 170 234 623 92...
output:
2.6999908898
result:
ok found '2.699990890', expected '2.699990890', error '0.000000000'
Test #13:
score: 5
Accepted
time: 141ms
memory: 9384kb
input:
20 429 28 7 29 517 731 130 50 922 756 346 214 605 401 347 26 336 745 288 515 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1215.3980758062
result:
ok found '1215.398075806', expected '1215.398075806', error '0.000000000'
Test #14:
score: 5
Accepted
time: 142ms
memory: 9384kb
input:
20 432 9 104 93 63 658 242 123 433 608 198 258 744 947 539 596 154 403 119 40 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1187.7239589422
result:
ok found '1187.723958942', expected '1187.723958942', error '0.000000000'
Test #15:
score: 5
Accepted
time: 141ms
memory: 9388kb
input:
20 436 757 968 388 378 584 355 195 177 228 51 302 115 726 964 934 204 828 949 797 1 1 1 1 1 1 1 1 1 ...
output:
1440.8091809506
result:
ok found '1440.809180951', expected '1440.809180951', error '0.000000000'
Test #16:
score: 5
Accepted
time: 147ms
memory: 9388kb
input:
20 439 505 64 683 693 511 467 268 688 80 903 346 486 272 388 504 254 485 780 553 1 1 1 1 1 1 1 1 1 1...
output:
1268.0985628407
result:
ok found '1268.098562841', expected '1268.098562841', error '0.000000000'
Test #17:
score: 5
Accepted
time: 148ms
memory: 9384kb
input:
20 442 486 928 746 239 438 580 341 432 932 755 390 625 50 580 842 304 910 611 310 723 313 522 392 65...
output:
1772.2437626123
result:
ok found '1772.243762612', expected '1772.243762612', error '0.000000000'
Test #18:
score: 5
Accepted
time: 149ms
memory: 9384kb
input:
20 446 234 24 42 554 364 692 414 943 784 607 434 995 597 4 412 354 568 441 835 370 794 769 407 259 4...
output:
1623.7563748623
result:
ok found '1623.756374862', expected '1623.756374862', error '0.000000000'
Test #19:
score: 5
Accepted
time: 144ms
memory: 9384kb
input:
20 449 983 888 337 868 291 37 486 687 635 459 478 366 375 428 750 172 225 272 591 786 507 784 654 94...
output:
1642.3014908766
result:
ok found '1642.301490877', expected '1642.301490877', error '0.000000000'
Test #20:
score: 5
Accepted
time: 146ms
memory: 9388kb
input:
20 452 963 985 632 415 218 149 559 199 255 311 523 505 921 620 320 222 650 103 348 201 988 31 668 69...
output:
1942.4791951147
result:
ok found '1942.479195115', expected '1942.479195115', error '0.000000000'
Extra Test:
score: 0
Extra Test Passed