QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#106091	#6372. Dance	Determinant	WA	3330ms	3848kb	C++14	724b	2023-05-16 15:02:13	2023-05-16 15:02:17

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-16 15:02:17]
评测

测评结果：WA
用时：3330ms
内存：3848kb

查看

[2023-05-16 15:02:13]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1e9,a[107],b[107],fl[107],A,B;
int sol(){
	for(int j=1;j<=n;++j)b[j]=a[j]+fl[j]*(m+m);sort(b+1,b+n+1);
	int s=A;for(int j=2;j<=n;++j)s+=min((b[j]-b[j-1])*B,A);return s; 
}
int main(){
	scanf("%d%d%d%d",&n,&m,&A,&B);for(int i=1;i<=n;++i)scanf("%d",&a[i]);srand(777);
	sort(a+1,a+n+1);for(int i=0;i<=n;++i){
		for(int j=1;j<=n;++j)fl[j]=(j<=i);ans=min(ans,sol());
	}
	for(int i=0;i<=400;++i){
		for(int j=1;j<=n;++j)fl[j]=rand()&1;int nw=sol();
		for(double t=1e6;t>1e-9;t*=0.999){
			int x=rand()%n+1,qt=0;fl[x]=!fl[x];int d=sol()-nw;
			if(d<0||exp((double)d/t)*RAND_MAX<rand())ans=min(ans,nw=nw+d);else fl[x]=!fl[x];
		}
	}
	printf("%d\n",ans);
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 627ms

memory: 3608kb

input:

3 1 2 1
4 1 7

output:

result:

ok 1 number(s): "5"

Test #2:

score: 0

Accepted

time: 642ms

memory: 3664kb

input:

3 1 7 1
4 1 7

output:

result:

ok 1 number(s): "11"

Test #3:

score: 0

Accepted

time: 400ms

memory: 3688kb

input:

1 1 441060 865580
6

output:

result:

ok 1 number(s): "441060"

Test #4:

score: 0

Accepted

time: 408ms

memory: 3552kb

input:

1 2 524484 157528
88

output:

result:

ok 1 number(s): "524484"

Test #5:

score: 0

Accepted

time: 408ms

memory: 3616kb

input:

1 3 607908 706373
65

output:

result:

ok 1 number(s): "607908"

Test #6:

score: 0

Accepted

time: 409ms

memory: 3740kb

input:

1 1 724036 287921
39

output:

result:

ok 1 number(s): "724036"

Test #7:

score: 0

Accepted

time: 410ms

memory: 3620kb

input:

1 4 807460 804061
17

output:

result:

ok 1 number(s): "807460"

Test #8:

score: 0

Accepted

time: 404ms

memory: 3688kb

input:

1 7 974308 869046
72

output:

result:

ok 1 number(s): "974308"

Test #9:

score: 0

Accepted

time: 422ms

memory: 3616kb

input:

1 4 221588 389967
17

output:

result:

ok 1 number(s): "221588"

Test #10:

score: 0

Accepted

time: 412ms

memory: 3780kb

input:

1 9 704116 877292
5

output:

result:

ok 1 number(s): "704116"

Test #11:

score: 0

Accepted

time: 409ms

memory: 3560kb

input:

1 3 820703 814856
86

output:

result:

ok 1 number(s): "820703"

Test #12:

score: 0

Accepted

time: 408ms

memory: 3544kb

input:

1 29 195626 207042
54

output:

result:

ok 1 number(s): "195626"

Test #13:

score: 0

Accepted

time: 409ms

memory: 3560kb

input:

1 19 794740 856124
14

output:

result:

ok 1 number(s): "794740"

Test #14:

score: 0

Accepted

time: 409ms

memory: 3680kb

input:

1 28 444117 184242
58

output:

result:

ok 1 number(s): "444117"

Test #15:

score: 0

Accepted

time: 404ms

memory: 3616kb

input:

1 32 527541 733087
27

output:

result:

ok 1 number(s): "527541"

Test #16:

score: 0

Accepted

time: 406ms

memory: 3692kb

input:

1 21 610965 281931
9

output:

result:

ok 1 number(s): "610965"

Test #17:

score: 0

Accepted

time: 405ms

memory: 3552kb

input:

1 7 393855 215606
79

output:

result:

ok 1 number(s): "393855"

Test #18:

score: 0

Accepted

time: 501ms

memory: 3628kb

input:

2 1 228470 977748
3 41

output:

result:

ok 1 number(s): "456940"

Test #19:

score: 0

Accepted

time: 472ms

memory: 3692kb

input:

2 2 344598 526593
80 2

output:

result:

ok 1 number(s): "689196"

Test #20:

score: 0

Accepted

time: 503ms

memory: 3664kb

input:

2 2 428022 42733
62 56

output:

result:

ok 1 number(s): "513488"

Test #21:

score: 0

Accepted

time: 467ms

memory: 3544kb

input:

2 2 511446 591577
28 9

output:

result:

ok 1 number(s): "1022892"

Test #22:

score: 0

Accepted

time: 474ms

memory: 3600kb

input:

2 1 594870 883526
5 67

output:

result:

ok 1 number(s): "1189740"

Test #23:

score: 0

Accepted

time: 512ms

memory: 3752kb

input:

2 2 794422 13919
65 74

output:

result:

ok 1 number(s): "864017"

Test #24:

score: 0

Accepted

time: 481ms

memory: 3784kb

input:

2 1 883770 771924
1 15

output:

result:

ok 1 number(s): "1767540"

Test #25:

score: 0

Accepted

time: 469ms

memory: 3560kb

input:

2 1 333594 259250
89 95

output:

result:

ok 1 number(s): "667188"

Test #26:

score: 0

Accepted

time: 487ms

memory: 3552kb

input:

2 11 482884 164110
69 4

output:

result:

ok 1 number(s): "965768"

Test #27:

score: 0

Accepted

time: 467ms

memory: 3552kb

input:

2 14 49295 556296
29 97

output:

result:

ok 1 number(s): "98590"

Test #28:

score: 0

Accepted

time: 560ms

memory: 3564kb

input:

2 12 424218 948481
98 86

output:

result:

ok 1 number(s): "848436"

Test #29:

score: 0

Accepted

time: 471ms

memory: 3544kb

input:

2 17 73594 533496
33 77

output:

result:

ok 1 number(s): "147188"

Test #30:

score: 0

Accepted

time: 549ms

memory: 3496kb

input:

2 25 157018 49636
15 38

output:

result:

ok 1 number(s): "314036"

Test #31:

score: 0

Accepted

time: 653ms

memory: 3684kb

input:

2 11 273146 631185
92 92

output:

result:

ok 1 number(s): "273146"

Test #32:

score: 0

Accepted

time: 561ms

memory: 3448kb

input:

2 34 23333 340667
58 79

output:

result:

ok 1 number(s): "46666"

Test #33:

score: 0

Accepted

time: 528ms

memory: 3680kb

input:

3 1 791688 281405
92 12 7

output:

result:

ok 1 number(s): "2375064"

Test #34:

score: 0

Accepted

time: 613ms

memory: 3684kb

input:

3 1 907816 606057
73 61 76

output:

result:

ok 1 number(s): "2421689"

Test #35:

score: 0

Accepted

time: 609ms

memory: 3684kb

input:

3 2 991240 154901
43 23 53

output:

result:

ok 1 number(s): "2911886"

Test #36:

score: 0

Accepted

time: 513ms

memory: 3732kb

input:

3 2 107368 703746
20 76 30

output:

result:

ok 1 number(s): "322104"

Test #37:

score: 0

Accepted

time: 536ms

memory: 3696kb

input:

3 5 158088 252590
2 30 94

output:

result:

ok 1 number(s): "474264"

Test #38:

score: 0

Accepted

time: 606ms

memory: 3780kb

input:

3 5 390344 317575
61 41 44

output:

result:

ok 1 number(s): "1171032"

Test #39:

score: 0

Accepted

time: 515ms

memory: 3500kb

input:

3 6 513247 896986
88 3 16

output:

result:

ok 1 number(s): "1539741"

Test #40:

score: 0

Accepted

time: 744ms

memory: 3624kb

input:

3 15 963072 384312
72 83 85

output:

result:

ok 1 number(s): "2694768"

Test #41:

score: 0

Accepted

time: 529ms

memory: 3628kb

input:

3 12 112362 513363
44 96 5

output:

result:

ok 1 number(s): "337086"

Test #42:

score: 0

Accepted

time: 580ms

memory: 3624kb

input:

3 20 711477 872845
13 85 98

output:

result:

ok 1 number(s): "2134431"

Test #43:

score: 0

Accepted

time: 673ms

memory: 3556kb

input:

3 29 310592 297735
69 74 90

output:

result:

ok 1 number(s): "931776"

Test #44:

score: 0

Accepted

time: 601ms

memory: 3732kb

input:

3 12 959968 882750
20 65 8

output:

result:

ok 1 number(s): "2879904"

Test #45:

score: 0

Accepted

time: 575ms

memory: 3560kb

input:

3 18 43392 431594
94 22 73

output:

result:

ok 1 number(s): "130176"

Test #46:

score: 0

Accepted

time: 651ms

memory: 3564kb

input:

3 11 126816 756246
68 76 50

output:

result:

ok 1 number(s): "380448"

Test #47:

score: 0

Accepted

time: 658ms

memory: 3616kb

input:

3 49 685514 689921
41 59 83

output:

result:

ok 1 number(s): "2056542"

Test #48:

score: 0

Accepted

time: 951ms

memory: 3684kb

input:

10 1 251127 64273
86 86 27 41 99 63 58 16 98 14

output:

result:

ok 1 number(s): "1763854"

Test #49:

score: 0

Accepted

time: 905ms

memory: 3844kb

input:

10 2 334552 580414
67 40 92 25 91 27 40 56 42 4

output:

result:

ok 1 number(s): "3010968"

Test #50:

score: 0

Accepted

time: 940ms

memory: 3756kb

input:

10 3 417976 905066
45 1 69 100 75 82 22 99 85 94

output:

result:

ok 1 number(s): "3343808"

Test #51:

score: 0

Accepted

time: 963ms

memory: 3664kb

input:

10 1 534104 453910
19 55 41 83 59 38 4 39 25 85

output:

result:

ok 1 number(s): "4192638"

Test #52:

score: 0

Accepted

time: 914ms

memory: 3764kb

input:

10 1 617528 2755
96 4 10 67 47 97 87 83 69 83

output:

result:

ok 1 number(s): "868233"

Test #53:

score: 0

Accepted

time: 1025ms

memory: 3628kb

input:

10 6 784376 67739
51 19 60 25 23 16 51 66 64 68

output:

result:

ok 1 number(s): "2652576"

Test #54:

score: 0

Accepted

time: 861ms

memory: 3612kb

input:

10 3 624048 730227
9 22 29 1 17 18 86 58 63 47

output:

result:

ok 1 number(s): "6240480"

Test #55:

score: 0

Accepted

time: 988ms

memory: 3628kb

input:

10 14 73873 217553
97 98 93 1 57 8 93 72 86 6

output:

result:

ok 1 number(s): "664857"

Test #56:

score: 0

Accepted

time: 969ms

memory: 3632kb

input:

10 3 966267 122413
77 15 21 60 56 60 4 73 31 50

output:

result:

ok 1 number(s): "5565813"

Test #57:

score: 0

Accepted

time: 963ms

memory: 3636kb

input:

10 5 565382 514598
45 95 14 30 92 5 10 72 96 49

output:

result:

ok 1 number(s): "5552252"

Test #58:

score: 0

Accepted

time: 1074ms

memory: 3692kb

input:

10 27 164497 163680
2 88 7 89 35 38 17 83 56 48

output:

result:

ok 1 number(s): "1315159"

Test #59:

score: 0

Accepted

time: 1071ms

memory: 3660kb

input:

10 47 813873 491799
49 83 20 52 51 47 96 76 62 96

output:

result:

ok 1 number(s): "7002783"

Test #60:

score: 0

Accepted

time: 1143ms

memory: 3804kb

input:

10 41 897297 40643
19 37 85 35 43 6 79 16 5 86

output:

result:

ok 1 number(s): "2766875"

Test #61:

score: 0

Accepted

time: 1035ms

memory: 3756kb

input:

10 21 13425 622191
96 98 66 19 31 62 57 59 53 76

output:

result:

ok 1 number(s): "134250"

Test #62:

score: 0

Accepted

time: 1053ms

memory: 3656kb

input:

10 28 763611 555866
70 81 99 56 78 80 35 94 12 55

output:

result:

ok 1 number(s): "7220620"

Test #63:

score: 0

Accepted

time: 3125ms

memory: 3760kb

input:

50 1 25934 980199
7 38 53 71 65 42 31 57 74 74 59 35 2 33 12 14 70 90 52 78 69 7 17 55 71 21 21 83 42 14 42 61 84 2 79 88 9 67 9 32 27 6 23 40 73 91 98 95 8 68

output:

result:

ok 1 number(s): "752086"

Test #64:

score: 0

Accepted

time: 3169ms

memory: 3848kb

input:

50 1 109358 496340
89 96 30 54 49 1 13 1 18 65 92 50 20 51 62 32 23 30 38 92 40 64 33 76 32 34 91 1 20 17 79 69 80 36 50 22 16 64 24 13 86 94 7 48 13 5 69 13 56 65

output:

result:

ok 1 number(s): "2733950"

Test #65:

score: 0

Accepted

time: 3187ms

memory: 3688kb

input:

50 1 225486 77888
62 53 94 29 41 61 95 40 62 55 33 73 29 73 21 50 64 83 20 1 23 21 50 97 85 50 62 27 86 4 11 78 88 62 25 59 27 65 34 2 32 83 90 59 57 23 24 23 3 47

output:

result:

ok 1 number(s): "4239058"

Test #66:

score: 0

Accepted

time: 3330ms

memory: 3612kb

input:

50 4 308910 626732
40 7 71 16 29 16 77 84 9 57 63 84 46 92 75 72 8 31 97 10 3 86 58 14 46 62 32 53 69 95 48 83 88 96 96 1 41 53 57 87 87 80 66 71 1 37 95 36 55 32

output:

result:

ok 1 number(s): "8340570"

Test #67:

score: -100

Wrong Answer

time: 3072ms

memory: 3680kb

input:

50 1 392334 142873
13 60 44 96 17 76 60 24 53 47 4 11 63 14 33 90 57 80 83 24 90 43 66 35 99 87 98 71 39 83 80 92 96 21 71 38 52 50 71 72 45 68 49 83 37 59 49 62 7 25

output:

result:

wrong answer 1st numbers differ - expected: '8420439', found: '8456724'