ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624 | #113. 【0621 模拟赛】Zrinka | taccat | 100 | 1989ms | 394688kb | C++14 | 751b | 2025-06-21 15:01:44 | 2025-06-21 23:50:04 |
answer
#include<bits/stdc++.h>
#define ll long long
const ll N=5e3;
using namespace std;
ll n,m,a[N+5],b[N+5],dp[N+5][N+5][2];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i][0][a[i]]=dp[i-1][0][a[i-1]]+(a[i]==a[i-1]);
dp[i][0][!a[i]]=0x3f3f3f3f3f3f3f3f;
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>b[i];
dp[0][i][b[i]]=dp[0][i-1][b[i-1]]+(b[i]==b[i-1]);
dp[0][i][!b[i]]=0x3f3f3f3f3f3f3f3f;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=1;k++){
dp[i][j][k]=min(a[i]==k?min(dp[i-1][j][(bool)k]+1,dp[i-1][j][!(bool)k]):0x3f3f3f3f3f3f3f3f,b[j]==k?min(dp[i][j-1][(bool)k]+1,dp[i][j-1][!(bool)k]):0x3f3f3f3f3f3f3f3f);
}
}
}
cout<<n+m+min(dp[n][m][1],dp[n][m][0]);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 1ms
memory: 3168kb
input:
0 500 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 ...
output:
750
result:
ok "750"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3296kb
input:
0 500 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 ...
output:
737
result:
ok "737"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
0 500 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 ...
output:
756
result:
ok "756"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
0 500 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 ...
output:
745
result:
ok "745"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3292kb
input:
0 500 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 ...
output:
738
result:
ok "738"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3340kb
input:
0 500 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 ...
output:
753
result:
ok "753"
Subtask #2:
score: 20
Accepted
Test #7:
score: 20
Accepted
time: 1ms
memory: 42580kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1490
result:
ok "1490"
Test #8:
score: 0
Accepted
time: 1ms
memory: 42576kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1468
result:
ok "1468"
Test #9:
score: 0
Accepted
time: 1ms
memory: 42652kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1516
result:
ok "1516"
Test #10:
score: 0
Accepted
time: 2ms
memory: 42540kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1502
result:
ok "1502"
Test #11:
score: 0
Accepted
time: 0ms
memory: 42448kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1484
result:
ok "1484"
Test #12:
score: 0
Accepted
time: 2ms
memory: 42512kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1502
result:
ok "1502"
Subtask #3:
score: 20
Accepted
Test #13:
score: 20
Accepted
time: 2ms
memory: 42504kb
input:
500 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 ...
output:
1088
result:
ok "1088"
Test #14:
score: 0
Accepted
time: 3ms
memory: 42508kb
input:
500 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 ...
output:
1100
result:
ok "1100"
Test #15:
score: 0
Accepted
time: 2ms
memory: 42536kb
input:
500 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 ...
output:
1089
result:
ok "1089"
Test #16:
score: 0
Accepted
time: 1ms
memory: 42652kb
input:
500 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 ...
output:
1099
result:
ok "1099"
Test #17:
score: 0
Accepted
time: 2ms
memory: 42500kb
input:
500 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 ...
output:
1085
result:
ok "1085"
Test #18:
score: 0
Accepted
time: 2ms
memory: 42500kb
input:
500 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 ...
output:
1087
result:
ok "1087"
Subtask #4:
score: 7
Accepted
Test #19:
score: 7
Accepted
time: 165ms
memory: 394524kb
input:
5000 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0...
output:
10836
result:
ok "10836"
Test #20:
score: 0
Accepted
time: 163ms
memory: 394536kb
input:
5000 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0...
output:
10782
result:
ok "10782"
Test #21:
score: 0
Accepted
time: 161ms
memory: 394408kb
input:
5000 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0...
output:
10795
result:
ok "10795"
Test #22:
score: 0
Accepted
time: 163ms
memory: 394536kb
input:
5000 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0...
output:
10830
result:
ok "10830"
Test #23:
score: 0
Accepted
time: 165ms
memory: 394688kb
input:
5000 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1...
output:
10809
result:
ok "10809"
Test #24:
score: 0
Accepted
time: 165ms
memory: 394640kb
input:
5000 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0...
output:
10743
result:
ok "10743"
Test #25:
score: 0
Accepted
time: 163ms
memory: 394408kb
input:
5000 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1...
output:
10801
result:
ok "10801"
Test #26:
score: 0
Accepted
time: 166ms
memory: 394564kb
input:
5000 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0...
output:
10786
result:
ok "10786"
Test #27:
score: 0
Accepted
time: 163ms
memory: 394652kb
input:
5000 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1...
output:
10778
result:
ok "10778"
Test #28:
score: 0
Accepted
time: 164ms
memory: 394564kb
input:
5000 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0...
output:
10810
result:
ok "10810"
Test #29:
score: 0
Accepted
time: 162ms
memory: 394488kb
input:
5000 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1...
output:
10750
result:
ok "10750"
Test #30:
score: 0
Accepted
time: 165ms
memory: 394572kb
input:
5000 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0...
output:
10804
result:
ok "10804"