oj.uz

Submission #967135

# Submission time Handle Problem Language Result Execution time Memory
967135 2024-04-21T09:05:18 Z ttamx Lamps (JOI19_lamps) C++17
4 / 100
 112 ms 27832 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int n;
char a[N],b[N];
int dp[N][3][2];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> (a+1) >> (b+1);
    for(int i=0;i<=n;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)dp[i][j][k]=2*n;
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int tl=0;tl<2;tl++)for(int tr=0;tr<2;tr++){
        if(j&&k&&j!=k)continue;
        int v=a[i]-'0';
        if(j)v=j-1;
        else if(k)v=k-1;
        v^=tl;
        if(v==b[i]-'0')dp[i][k][tr]=min(dp[i][k][tr],dp[i-1][j][tl]+(j!=k)+(tl!=tr));
        else dp[i][k][tr]=min(dp[i][k][tr],dp[i-1][j][tl]+(j!=k)+(tl!=tr)+2);
    }
    cout << dp[n][0][0]/2;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 107 ms 27832 KB Output is correct
8 Correct 112 ms 27832 KB Output is correct
9 Correct 110 ms 27740 KB Output is correct
10 Correct 111 ms 27744 KB Output is correct
11 Correct 111 ms 27736 KB Output is correct
12 Correct 97 ms 27740 KB Output is correct
13 Correct 105 ms 27832 KB Output is correct
14 Correct 103 ms 27740 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -