QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#763854 | #6372. Dance | Kevin5307 | WA | 5ms | 8476kb | C++23 | 2.4kb | 2024-11-19 22:24:03 | 2024-11-19 22:24:07 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n,d,a,b;
int x[105];
int f[105][105],g[105][105];
int w[105][105][105];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d>>a>>b;
swap(a,b);
for(int i=1;i<=n;i++)
{
cin>>x[i];
x[i]-=d;
x[i]*=a;
}
sort(x+1,x+n+1);
d*=2*a;
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
memset(w,0x3f,sizeof(w));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
multiset<int> st;
for(int p=i;p<=j;p++)
st.insert(x[p]);
int tot=0;
auto it=next(st.begin());
while(it!=st.end())
{
tot+=min(b,*it-*prev(it));
it++;
}
for(int p=i;p<j;p++)
{
auto it=st.lower_bound(x[p]);
if(next(it)!=st.end()) tot-=min(b,*next(it)-*it);
if(it!=st.begin()) tot-=min(b,*it-*prev(it));
if(next(it)!=st.end()) if(it!=st.begin()) tot+=min(b,*next(it)-*prev(it));
st.erase(it);
st.insert(x[p]+d);
it=st.lower_bound(x[p]+d);
if(next(it)!=st.end()) tot+=min(b,*next(it)-*it);
if(it!=st.begin()) tot+=min(b,*it-*prev(it));
if(next(it)!=st.end()) if(it!=st.begin()) tot-=min(b,*next(it)-*prev(it));
w[i][p][j]=tot;
}
}
for(int i=1;i<=n;i++)
f[0][i]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
{
for(int k=i+1;k<=n;k++)
g[i][k]=min(g[i][k],f[j][i]+w[j+1][i][k]);
for(int k=i+1;k<=n;k++)
{
int mx=max(x[j]+d,x[i]);
int mn=min(x[i+1]+d,x[k+1]);
if(mn>=mx)
f[i][k]=min(f[i][k],g[j][i]+min(b,max(0,mn-mx)));
else
f[i][k]=min(f[i][k],g[j][i]+b);
}
}
int ans=inf;
for(int i=0;i<=n;i++)
ans=min(ans,g[i][n]);
int sum=0;
for(int i=2;i<=n;i++)
sum+=min(b,x[i]-x[i-1]);
ans=min(ans,sum);
cout<<ans+b<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8224kb
input:
3 1 2 1 4 1 7
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 2ms
memory: 8164kb
input:
3 1 7 1 4 1 7
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: 0
Accepted
time: 2ms
memory: 8464kb
input:
1 1 441060 865580 6
output:
441060
result:
ok 1 number(s): "441060"
Test #4:
score: 0
Accepted
time: 2ms
memory: 8432kb
input:
1 2 524484 157528 88
output:
524484
result:
ok 1 number(s): "524484"
Test #5:
score: 0
Accepted
time: 2ms
memory: 8168kb
input:
1 3 607908 706373 65
output:
607908
result:
ok 1 number(s): "607908"
Test #6:
score: 0
Accepted
time: 0ms
memory: 8164kb
input:
1 1 724036 287921 39
output:
724036
result:
ok 1 number(s): "724036"
Test #7:
score: 0
Accepted
time: 1ms
memory: 8224kb
input:
1 4 807460 804061 17
output:
807460
result:
ok 1 number(s): "807460"
Test #8:
score: 0
Accepted
time: 0ms
memory: 8460kb
input:
1 7 974308 869046 72
output:
974308
result:
ok 1 number(s): "974308"
Test #9:
score: 0
Accepted
time: 0ms
memory: 8224kb
input:
1 4 221588 389967 17
output:
221588
result:
ok 1 number(s): "221588"
Test #10:
score: 0
Accepted
time: 2ms
memory: 8220kb
input:
1 9 704116 877292 5
output:
704116
result:
ok 1 number(s): "704116"
Test #11:
score: 0
Accepted
time: 2ms
memory: 8268kb
input:
1 3 820703 814856 86
output:
820703
result:
ok 1 number(s): "820703"
Test #12:
score: 0
Accepted
time: 2ms
memory: 8228kb
input:
1 29 195626 207042 54
output:
195626
result:
ok 1 number(s): "195626"
Test #13:
score: 0
Accepted
time: 1ms
memory: 8164kb
input:
1 19 794740 856124 14
output:
794740
result:
ok 1 number(s): "794740"
Test #14:
score: 0
Accepted
time: 0ms
memory: 8160kb
input:
1 28 444117 184242 58
output:
444117
result:
ok 1 number(s): "444117"
Test #15:
score: 0
Accepted
time: 2ms
memory: 8264kb
input:
1 32 527541 733087 27
output:
527541
result:
ok 1 number(s): "527541"
Test #16:
score: 0
Accepted
time: 1ms
memory: 8472kb
input:
1 21 610965 281931 9
output:
610965
result:
ok 1 number(s): "610965"
Test #17:
score: 0
Accepted
time: 1ms
memory: 8164kb
input:
1 7 393855 215606 79
output:
393855
result:
ok 1 number(s): "393855"
Test #18:
score: 0
Accepted
time: 0ms
memory: 8428kb
input:
2 1 228470 977748 3 41
output:
456940
result:
ok 1 number(s): "456940"
Test #19:
score: 0
Accepted
time: 2ms
memory: 8200kb
input:
2 2 344598 526593 80 2
output:
689196
result:
ok 1 number(s): "689196"
Test #20:
score: 0
Accepted
time: 0ms
memory: 8428kb
input:
2 2 428022 42733 62 56
output:
513488
result:
ok 1 number(s): "513488"
Test #21:
score: 0
Accepted
time: 2ms
memory: 8476kb
input:
2 2 511446 591577 28 9
output:
1022892
result:
ok 1 number(s): "1022892"
Test #22:
score: 0
Accepted
time: 0ms
memory: 8228kb
input:
2 1 594870 883526 5 67
output:
1189740
result:
ok 1 number(s): "1189740"
Test #23:
score: 0
Accepted
time: 2ms
memory: 8396kb
input:
2 2 794422 13919 65 74
output:
864017
result:
ok 1 number(s): "864017"
Test #24:
score: 0
Accepted
time: 2ms
memory: 8260kb
input:
2 1 883770 771924 1 15
output:
1767540
result:
ok 1 number(s): "1767540"
Test #25:
score: 0
Accepted
time: 0ms
memory: 8260kb
input:
2 1 333594 259250 89 95
output:
667188
result:
ok 1 number(s): "667188"
Test #26:
score: 0
Accepted
time: 0ms
memory: 8428kb
input:
2 11 482884 164110 69 4
output:
965768
result:
ok 1 number(s): "965768"
Test #27:
score: 0
Accepted
time: 2ms
memory: 8172kb
input:
2 14 49295 556296 29 97
output:
98590
result:
ok 1 number(s): "98590"
Test #28:
score: 0
Accepted
time: 1ms
memory: 8232kb
input:
2 12 424218 948481 98 86
output:
848436
result:
ok 1 number(s): "848436"
Test #29:
score: 0
Accepted
time: 0ms
memory: 8428kb
input:
2 17 73594 533496 33 77
output:
147188
result:
ok 1 number(s): "147188"
Test #30:
score: 0
Accepted
time: 2ms
memory: 8232kb
input:
2 25 157018 49636 15 38
output:
314036
result:
ok 1 number(s): "314036"
Test #31:
score: 0
Accepted
time: 0ms
memory: 8164kb
input:
2 11 273146 631185 92 92
output:
273146
result:
ok 1 number(s): "273146"
Test #32:
score: 0
Accepted
time: 2ms
memory: 8464kb
input:
2 34 23333 340667 58 79
output:
46666
result:
ok 1 number(s): "46666"
Test #33:
score: 0
Accepted
time: 0ms
memory: 8476kb
input:
3 1 791688 281405 92 12 7
output:
2375064
result:
ok 1 number(s): "2375064"
Test #34:
score: 0
Accepted
time: 1ms
memory: 8228kb
input:
3 1 907816 606057 73 61 76
output:
2421689
result:
ok 1 number(s): "2421689"
Test #35:
score: 0
Accepted
time: 2ms
memory: 8160kb
input:
3 2 991240 154901 43 23 53
output:
2911886
result:
ok 1 number(s): "2911886"
Test #36:
score: 0
Accepted
time: 2ms
memory: 8476kb
input:
3 2 107368 703746 20 76 30
output:
322104
result:
ok 1 number(s): "322104"
Test #37:
score: 0
Accepted
time: 0ms
memory: 8228kb
input:
3 5 158088 252590 2 30 94
output:
474264
result:
ok 1 number(s): "474264"
Test #38:
score: 0
Accepted
time: 0ms
memory: 8172kb
input:
3 5 390344 317575 61 41 44
output:
1171032
result:
ok 1 number(s): "1171032"
Test #39:
score: 0
Accepted
time: 2ms
memory: 8224kb
input:
3 6 513247 896986 88 3 16
output:
1539741
result:
ok 1 number(s): "1539741"
Test #40:
score: 0
Accepted
time: 0ms
memory: 8160kb
input:
3 15 963072 384312 72 83 85
output:
2694768
result:
ok 1 number(s): "2694768"
Test #41:
score: 0
Accepted
time: 0ms
memory: 8268kb
input:
3 12 112362 513363 44 96 5
output:
337086
result:
ok 1 number(s): "337086"
Test #42:
score: 0
Accepted
time: 2ms
memory: 8396kb
input:
3 20 711477 872845 13 85 98
output:
2134431
result:
ok 1 number(s): "2134431"
Test #43:
score: 0
Accepted
time: 0ms
memory: 8228kb
input:
3 29 310592 297735 69 74 90
output:
931776
result:
ok 1 number(s): "931776"
Test #44:
score: 0
Accepted
time: 2ms
memory: 8228kb
input:
3 12 959968 882750 20 65 8
output:
2879904
result:
ok 1 number(s): "2879904"
Test #45:
score: 0
Accepted
time: 2ms
memory: 8172kb
input:
3 18 43392 431594 94 22 73
output:
130176
result:
ok 1 number(s): "130176"
Test #46:
score: 0
Accepted
time: 0ms
memory: 8164kb
input:
3 11 126816 756246 68 76 50
output:
380448
result:
ok 1 number(s): "380448"
Test #47:
score: 0
Accepted
time: 2ms
memory: 8392kb
input:
3 49 685514 689921 41 59 83
output:
2056542
result:
ok 1 number(s): "2056542"
Test #48:
score: 0
Accepted
time: 1ms
memory: 8200kb
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: 2ms
memory: 8168kb
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: 2ms
memory: 8232kb
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: 0ms
memory: 8164kb
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: 2ms
memory: 8472kb
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: 0ms
memory: 8260kb
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: 2ms
memory: 8224kb
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: 0ms
memory: 8476kb
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: 2ms
memory: 8476kb
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: 1ms
memory: 8200kb
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: 2ms
memory: 8180kb
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: 1ms
memory: 8428kb
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: 0ms
memory: 8172kb
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: 0ms
memory: 8108kb
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: 0ms
memory: 8228kb
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: 4ms
memory: 8164kb
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: 0
Accepted
time: 4ms
memory: 8164kb
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:
2733950
result:
ok 1 number(s): "2733950"
Test #65:
score: 0
Accepted
time: 4ms
memory: 8164kb
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:
4239058
result:
ok 1 number(s): "4239058"
Test #66:
score: 0
Accepted
time: 4ms
memory: 8116kb
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:
8340570
result:
ok 1 number(s): "8340570"
Test #67:
score: 0
Accepted
time: 4ms
memory: 8212kb
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:
8420439
result:
ok 1 number(s): "8420439"
Test #68:
score: 0
Accepted
time: 2ms
memory: 8232kb
input:
50 4 591886 16370 73 75 94 58 93 87 20 11 40 32 74 45 1 51 46 35 47 73 39 42 44 61 95 66 25 16 43 23 84 73 45 5 5 85 13 14 77 44 4 42 54 54 21 6 25 91 75 90 7 7
output:
1999706
result:
ok 1 number(s): "1999706"
Test #69:
score: 0
Accepted
time: 5ms
memory: 8236kb
input:
50 5 488402 58390 75 79 98 42 53 67 94 78 66 81 57 1 63 47 11 87 39 16 92 37 31 39 63 43 92 9 92 61 41 98 43 30 94 1 66 52 94 76 31 98 98 77 23 31 24 99 32 51 57 30
output:
4347598
result:
ok 1 number(s): "4347598"
Test #70:
score: 0
Accepted
time: 4ms
memory: 8168kb
input:
50 1 970930 545716 64 63 62 50 85 53 5 80 88 45 27 100 45 44 98 86 59 47 97 99 35 32 32 32 89 87 39 76 5 62 8 66 11 54 37 52 47 68 11 31 70 44 37 96 28 89 42 32 16 72
output:
22508686
result:
ok 1 number(s): "22508686"
Test #71:
score: -100
Wrong Answer
time: 5ms
memory: 8268kb
input:
50 18 863325 450576 32 72 91 13 88 9 4 77 30 88 58 7 73 96 55 88 17 4 56 53 59 66 69 11 10 56 18 55 58 5 11 23 41 37 6 99 53 86 27 1 96 68 2 93 40 58 65 74 3 95
output:
21060243
result:
wrong answer 1st numbers differ - expected: '20196918', found: '21060243'