UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203008#2451. Awosile1001698ms9424kbC++11827b2024-02-18 11:41:242024-02-18 13:24:02

answer

#include<bits/stdc++.h>
using namespace std;
double f[3000005];
int n;
int w[25],l[25];
inline int lowbit(int x){
	return x&(-x);
} 
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&l[i]);
	for(int i=0;i<n;i++)scanf("%d",&w[i]);
	for(int i=0;i<(1<<n)-1;i++){
		double sum=0;
		for(int j=0;j<n;j++)if((1<<j)&i)sum+=w[j];
		for(int j=0;j<n;j++)if(((i>>j)&1)==0){
			double d=l[j]*0.5*w[j]/(w[j]+sum);
			f[i|(1<<j)]=max(f[i|(1<<j)],max(f[i]+d,l[j]-d));
		}
//		printf("f[%d]=%.9lf\n",i,f[i]);
	}
	printf("%.10lf",f[(1<<n)-1]);
	return 0;
	// 从上到下一本一本考虑,一本书的右边界对齐上面所有书的重心。
	// f[mask] 即为选择 mask 书本时,重心到端的最大距离。 
	// 根据数学直觉,重心就是加权平均。 
	// quod erat demonstrandum
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1232kb

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: 1228kb

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: 1228kb

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: 1228kb

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: 1228kb

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: 1232kb

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: 1228kb

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: 1228kb

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: 145ms
memory: 9416kb

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: 136ms
memory: 9412kb

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: 138ms
memory: 9412kb

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: 145ms
memory: 9416kb

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: 143ms
memory: 9424kb

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: 147ms
memory: 9420kb

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: 144ms
memory: 9424kb

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: 131ms
memory: 9424kb

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: 145ms
memory: 9420kb

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: 141ms
memory: 9424kb

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: 136ms
memory: 9424kb

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: 147ms
memory: 9420kb

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