QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#825735 | #69. Lamps | guleng2007 | 4 | 30ms | 21484kb | C++20 | 815b | 2024-12-21 22:08:35 | 2024-12-21 22:08:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int dp[N][2][2];
char s[N], t[N];
int main()
{
int n;
cin >> n;
scanf("%s",s+1);
scanf("%s",t+1);
memset(dp,0x3f,sizeof(dp));
dp[0][0][0]=0;
for(int i=0;i<n;i++)
for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++)
if(dp[i][j][k]<=100000000)
{
for(int newj=0;newj<=1;newj++)
{
int cost=0;
if(newj==1 && j==0)
cost++;
for(int newk=newj^(s[i+1]!=t[i+1]);newk<=1;newk++)
{
if(newk && (!k || t[i]!=t[i+1]))
cost++;
dp[i+1][newj][newk]=min(dp[i+1][newj][newk],dp[i][j][k]+cost);
}
}
}
int ans=0x3f3f3f3f;
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
ans=min(ans,dp[n][i][j]);
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 20212kb
input:
1 1 0
output:
1
result:
ok single line: '1'
Test #2:
score: 6
Accepted
time: 4ms
memory: 20808kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 6
Accepted
time: 4ms
memory: 20444kb
input:
2 10 01
output:
1
result:
ok single line: '1'
Test #4:
score: 6
Accepted
time: 0ms
memory: 20712kb
input:
2 01 10
output:
1
result:
ok single line: '1'
Test #5:
score: 6
Accepted
time: 4ms
memory: 20720kb
input:
2 11 00
output:
1
result:
ok single line: '1'
Test #6:
score: 6
Accepted
time: 0ms
memory: 20808kb
input:
2 11 10
output:
1
result:
ok single line: '1'
Test #7:
score: 6
Accepted
time: 4ms
memory: 19536kb
input:
2 11 01
output:
1
result:
ok single line: '1'
Test #8:
score: 6
Accepted
time: 0ms
memory: 20912kb
input:
18 000000000000000000 101010101010101010
output:
9
result:
ok single line: '9'
Test #9:
score: 6
Accepted
time: 0ms
memory: 19532kb
input:
18 111111111111111111 010101010101010101
output:
9
result:
ok single line: '9'
Test #10:
score: 6
Accepted
time: 0ms
memory: 19596kb
input:
17 11111111111111111 10101010101010101
output:
8
result:
ok single line: '8'
Test #11:
score: 6
Accepted
time: 0ms
memory: 20340kb
input:
17 00000000000000000 01010101010101010
output:
8
result:
ok single line: '8'
Test #12:
score: 6
Accepted
time: 0ms
memory: 20316kb
input:
18 110111100010101111 010111100011100000
output:
3
result:
ok single line: '3'
Test #13:
score: 6
Accepted
time: 4ms
memory: 20580kb
input:
17 10110110110110101 01011100100110000
output:
4
result:
ok single line: '4'
Test #14:
score: 6
Accepted
time: 0ms
memory: 20048kb
input:
18 000000110001001000 111111001011011100
output:
3
result:
ok single line: '3'
Test #15:
score: 6
Accepted
time: 0ms
memory: 20476kb
input:
17 11011010101011111 10011000100000101
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 20884kb
input:
18 011011101011011000 001010011011110001
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 4
Accepted
Test #59:
score: 4
Accepted
time: 0ms
memory: 21028kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #60:
score: 4
Accepted
time: 0ms
memory: 19780kb
input:
1 0 1
output:
1
result:
ok single line: '1'
Test #61:
score: 4
Accepted
time: 4ms
memory: 20664kb
input:
2 00 00
output:
0
result:
ok single line: '0'
Test #62:
score: 4
Accepted
time: 0ms
memory: 19724kb
input:
2 00 10
output:
1
result:
ok single line: '1'
Test #63:
score: 4
Accepted
time: 0ms
memory: 20976kb
input:
2 00 01
output:
1
result:
ok single line: '1'
Test #64:
score: 4
Accepted
time: 0ms
memory: 19840kb
input:
2 00 11
output:
1
result:
ok single line: '1'
Test #65:
score: 4
Accepted
time: 30ms
memory: 21480kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok single line: '0'
Test #66:
score: 4
Accepted
time: 25ms
memory: 21424kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #67:
score: 4
Accepted
time: 24ms
memory: 21432kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #68:
score: 4
Accepted
time: 25ms
memory: 21308kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #69:
score: 4
Accepted
time: 23ms
memory: 21360kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
499999
result:
ok single line: '499999'
Test #70:
score: 4
Accepted
time: 23ms
memory: 21484kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1
result:
ok single line: '1'
Test #71:
score: 4
Accepted
time: 29ms
memory: 21484kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100
result:
ok single line: '100'
Test #72:
score: 4
Accepted
time: 25ms
memory: 21360kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12345
result:
ok single line: '12345'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%