QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #106090 | #6372. Dance | Determinant | WA | 299ms | 3848kb | C++14 | 723b | 2023-05-16 15:01:08 | 2023-05-16 15:01:10 |
Judging History
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<=40;++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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 67ms
memory: 3760kb
input:
3 1 2 1 4 1 7
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 67ms
memory: 3848kb
input:
3 1 7 1 4 1 7
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: 0
Accepted
time: 41ms
memory: 3540kb
input:
1 1 441060 865580 6
output:
441060
result:
ok 1 number(s): "441060"
Test #4:
score: 0
Accepted
time: 44ms
memory: 3692kb
input:
1 2 524484 157528 88
output:
524484
result:
ok 1 number(s): "524484"
Test #5:
score: 0
Accepted
time: 45ms
memory: 3680kb
input:
1 3 607908 706373 65
output:
607908
result:
ok 1 number(s): "607908"
Test #6:
score: 0
Accepted
time: 46ms
memory: 3624kb
input:
1 1 724036 287921 39
output:
724036
result:
ok 1 number(s): "724036"
Test #7:
score: 0
Accepted
time: 45ms
memory: 3620kb
input:
1 4 807460 804061 17
output:
807460
result:
ok 1 number(s): "807460"
Test #8:
score: 0
Accepted
time: 44ms
memory: 3780kb
input:
1 7 974308 869046 72
output:
974308
result:
ok 1 number(s): "974308"
Test #9:
score: 0
Accepted
time: 45ms
memory: 3540kb
input:
1 4 221588 389967 17
output:
221588
result:
ok 1 number(s): "221588"
Test #10:
score: 0
Accepted
time: 45ms
memory: 3532kb
input:
1 9 704116 877292 5
output:
704116
result:
ok 1 number(s): "704116"
Test #11:
score: 0
Accepted
time: 40ms
memory: 3736kb
input:
1 3 820703 814856 86
output:
820703
result:
ok 1 number(s): "820703"
Test #12:
score: 0
Accepted
time: 45ms
memory: 3692kb
input:
1 29 195626 207042 54
output:
195626
result:
ok 1 number(s): "195626"
Test #13:
score: 0
Accepted
time: 41ms
memory: 3620kb
input:
1 19 794740 856124 14
output:
794740
result:
ok 1 number(s): "794740"
Test #14:
score: 0
Accepted
time: 45ms
memory: 3544kb
input:
1 28 444117 184242 58
output:
444117
result:
ok 1 number(s): "444117"
Test #15:
score: 0
Accepted
time: 45ms
memory: 3736kb
input:
1 32 527541 733087 27
output:
527541
result:
ok 1 number(s): "527541"
Test #16:
score: 0
Accepted
time: 41ms
memory: 3736kb
input:
1 21 610965 281931 9
output:
610965
result:
ok 1 number(s): "610965"
Test #17:
score: 0
Accepted
time: 47ms
memory: 3544kb
input:
1 7 393855 215606 79
output:
393855
result:
ok 1 number(s): "393855"
Test #18:
score: 0
Accepted
time: 46ms
memory: 3784kb
input:
2 1 228470 977748 3 41
output:
456940
result:
ok 1 number(s): "456940"
Test #19:
score: 0
Accepted
time: 50ms
memory: 3676kb
input:
2 2 344598 526593 80 2
output:
689196
result:
ok 1 number(s): "689196"
Test #20:
score: 0
Accepted
time: 64ms
memory: 3680kb
input:
2 2 428022 42733 62 56
output:
513488
result:
ok 1 number(s): "513488"
Test #21:
score: 0
Accepted
time: 47ms
memory: 3532kb
input:
2 2 511446 591577 28 9
output:
1022892
result:
ok 1 number(s): "1022892"
Test #22:
score: 0
Accepted
time: 51ms
memory: 3740kb
input:
2 1 594870 883526 5 67
output:
1189740
result:
ok 1 number(s): "1189740"
Test #23:
score: 0
Accepted
time: 50ms
memory: 3744kb
input:
2 2 794422 13919 65 74
output:
864017
result:
ok 1 number(s): "864017"
Test #24:
score: 0
Accepted
time: 47ms
memory: 3624kb
input:
2 1 883770 771924 1 15
output:
1767540
result:
ok 1 number(s): "1767540"
Test #25:
score: 0
Accepted
time: 51ms
memory: 3784kb
input:
2 1 333594 259250 89 95
output:
667188
result:
ok 1 number(s): "667188"
Test #26:
score: 0
Accepted
time: 51ms
memory: 3736kb
input:
2 11 482884 164110 69 4
output:
965768
result:
ok 1 number(s): "965768"
Test #27:
score: 0
Accepted
time: 47ms
memory: 3692kb
input:
2 14 49295 556296 29 97
output:
98590
result:
ok 1 number(s): "98590"
Test #28:
score: 0
Accepted
time: 60ms
memory: 3548kb
input:
2 12 424218 948481 98 86
output:
848436
result:
ok 1 number(s): "848436"
Test #29:
score: 0
Accepted
time: 51ms
memory: 3732kb
input:
2 17 73594 533496 33 77
output:
147188
result:
ok 1 number(s): "147188"
Test #30:
score: 0
Accepted
time: 59ms
memory: 3528kb
input:
2 25 157018 49636 15 38
output:
314036
result:
ok 1 number(s): "314036"
Test #31:
score: 0
Accepted
time: 69ms
memory: 3844kb
input:
2 11 273146 631185 92 92
output:
273146
result:
ok 1 number(s): "273146"
Test #32:
score: 0
Accepted
time: 60ms
memory: 3552kb
input:
2 34 23333 340667 58 79
output:
46666
result:
ok 1 number(s): "46666"
Test #33:
score: 0
Accepted
time: 50ms
memory: 3544kb
input:
3 1 791688 281405 92 12 7
output:
2375064
result:
ok 1 number(s): "2375064"
Test #34:
score: 0
Accepted
time: 66ms
memory: 3660kb
input:
3 1 907816 606057 73 61 76
output:
2421689
result:
ok 1 number(s): "2421689"
Test #35:
score: 0
Accepted
time: 67ms
memory: 3616kb
input:
3 2 991240 154901 43 23 53
output:
2911886
result:
ok 1 number(s): "2911886"
Test #36:
score: 0
Accepted
time: 50ms
memory: 3628kb
input:
3 2 107368 703746 20 76 30
output:
322104
result:
ok 1 number(s): "322104"
Test #37:
score: 0
Accepted
time: 50ms
memory: 3540kb
input:
3 5 158088 252590 2 30 94
output:
474264
result:
ok 1 number(s): "474264"
Test #38:
score: 0
Accepted
time: 62ms
memory: 3532kb
input:
3 5 390344 317575 61 41 44
output:
1171032
result:
ok 1 number(s): "1171032"
Test #39:
score: 0
Accepted
time: 54ms
memory: 3624kb
input:
3 6 513247 896986 88 3 16
output:
1539741
result:
ok 1 number(s): "1539741"
Test #40:
score: 0
Accepted
time: 80ms
memory: 3628kb
input:
3 15 963072 384312 72 83 85
output:
2694768
result:
ok 1 number(s): "2694768"
Test #41:
score: 0
Accepted
time: 54ms
memory: 3568kb
input:
3 12 112362 513363 44 96 5
output:
337086
result:
ok 1 number(s): "337086"
Test #42:
score: 0
Accepted
time: 63ms
memory: 3620kb
input:
3 20 711477 872845 13 85 98
output:
2134431
result:
ok 1 number(s): "2134431"
Test #43:
score: 0
Accepted
time: 69ms
memory: 3624kb
input:
3 29 310592 297735 69 74 90
output:
931776
result:
ok 1 number(s): "931776"
Test #44:
score: 0
Accepted
time: 64ms
memory: 3740kb
input:
3 12 959968 882750 20 65 8
output:
2879904
result:
ok 1 number(s): "2879904"
Test #45:
score: 0
Accepted
time: 60ms
memory: 3676kb
input:
3 18 43392 431594 94 22 73
output:
130176
result:
ok 1 number(s): "130176"
Test #46:
score: 0
Accepted
time: 68ms
memory: 3692kb
input:
3 11 126816 756246 68 76 50
output:
380448
result:
ok 1 number(s): "380448"
Test #47:
score: 0
Accepted
time: 68ms
memory: 3548kb
input:
3 49 685514 689921 41 59 83
output:
2056542
result:
ok 1 number(s): "2056542"
Test #48:
score: 0
Accepted
time: 99ms
memory: 3676kb
input:
10 1 251127 64273 86 86 27 41 99 63 58 16 98 14
output:
1763854
result:
ok 1 number(s): "1763854"
Test #49:
score: 0
Accepted
time: 88ms
memory: 3740kb
input:
10 2 334552 580414 67 40 92 25 91 27 40 56 42 4
output:
3010968
result:
ok 1 number(s): "3010968"
Test #50:
score: 0
Accepted
time: 92ms
memory: 3632kb
input:
10 3 417976 905066 45 1 69 100 75 82 22 99 85 94
output:
3343808
result:
ok 1 number(s): "3343808"
Test #51:
score: 0
Accepted
time: 99ms
memory: 3800kb
input:
10 1 534104 453910 19 55 41 83 59 38 4 39 25 85
output:
4192638
result:
ok 1 number(s): "4192638"
Test #52:
score: 0
Accepted
time: 92ms
memory: 3624kb
input:
10 1 617528 2755 96 4 10 67 47 97 87 83 69 83
output:
868233
result:
ok 1 number(s): "868233"
Test #53:
score: 0
Accepted
time: 100ms
memory: 3660kb
input:
10 6 784376 67739 51 19 60 25 23 16 51 66 64 68
output:
2652576
result:
ok 1 number(s): "2652576"
Test #54:
score: 0
Accepted
time: 82ms
memory: 3688kb
input:
10 3 624048 730227 9 22 29 1 17 18 86 58 63 47
output:
6240480
result:
ok 1 number(s): "6240480"
Test #55:
score: 0
Accepted
time: 101ms
memory: 3688kb
input:
10 14 73873 217553 97 98 93 1 57 8 93 72 86 6
output:
664857
result:
ok 1 number(s): "664857"
Test #56:
score: 0
Accepted
time: 98ms
memory: 3744kb
input:
10 3 966267 122413 77 15 21 60 56 60 4 73 31 50
output:
5565813
result:
ok 1 number(s): "5565813"
Test #57:
score: 0
Accepted
time: 92ms
memory: 3612kb
input:
10 5 565382 514598 45 95 14 30 92 5 10 72 96 49
output:
5552252
result:
ok 1 number(s): "5552252"
Test #58:
score: 0
Accepted
time: 101ms
memory: 3796kb
input:
10 27 164497 163680 2 88 7 89 35 38 17 83 56 48
output:
1315159
result:
ok 1 number(s): "1315159"
Test #59:
score: 0
Accepted
time: 106ms
memory: 3800kb
input:
10 47 813873 491799 49 83 20 52 51 47 96 76 62 96
output:
7002783
result:
ok 1 number(s): "7002783"
Test #60:
score: 0
Accepted
time: 111ms
memory: 3620kb
input:
10 41 897297 40643 19 37 85 35 43 6 79 16 5 86
output:
2766875
result:
ok 1 number(s): "2766875"
Test #61:
score: 0
Accepted
time: 105ms
memory: 3780kb
input:
10 21 13425 622191 96 98 66 19 31 62 57 59 53 76
output:
134250
result:
ok 1 number(s): "134250"
Test #62:
score: 0
Accepted
time: 103ms
memory: 3660kb
input:
10 28 763611 555866 70 81 99 56 78 80 35 94 12 55
output:
7220620
result:
ok 1 number(s): "7220620"
Test #63:
score: 0
Accepted
time: 299ms
memory: 3680kb
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:
752086
result:
ok 1 number(s): "752086"
Test #64:
score: -100
Wrong Answer
time: 293ms
memory: 3800kb
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:
2843308
result:
wrong answer 1st numbers differ - expected: '2733950', found: '2843308'