oj.uz

Submission #545094

# Submission time Handle Problem Language Result Execution time Memory
545094 2022-04-03T14:43:19 Z chonka Lamps (JOI19_lamps) C++
4 / 100
 14 ms 8416 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

#define MAXN 1000007

int n ;
string a , b ;

int dp[ MAXN ] ;

void input ( ) {
    cin >> n >> a >> b ;
}

void solve ( ) {
    int diff = 0 ;
    int mn_0 , mn_1 ;
    mn_0 = mn_1 = 3 * MAXN ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        dp[ i ] = MAXN ;
        if ( a[ i - 1 ] == b[ i - 1 ] ) {
            dp[ i ] = min ( dp[ i ] , dp[ i - 1 ] ) ;
        }
        if ( i > 1 && b[ i - 1 ] != b[ i - 2 ] ) {
            ++ mn_0 , ++ mn_1 ;
        }
        if ( b[ i - 1 ] == '0' ) {
            dp[ i ] = min ( dp[ i ] , ( mn_0 + 1 ) / 2 ) ;
        }
        else {
            dp[ i ] = min ( dp[ i ] , ( mn_1 + 1 ) / 2 ) ;
        }
        
        if ( a[ i - 1 ] != b[ i - 1 ] ) { ++ diff ; }
        else { diff = 0 ; }
        if ( diff > 0 ) {
            dp[ i ] = min ( dp[ i ] , dp[ i - diff ] + 1 ) ;
        }

        if ( b[ i - 1 ] == '0' ) {
            mn_0 = min ( mn_0 , 2 * dp[ i - 1 ] + 1 ) ;
        }
        else {
            mn_1 = min ( mn_1 , 2 * dp[ i - 1 ] + 1 ) ;
        }
    }
    cout << dp[ n ] << "\n" ;
}

int main ( ) {
    //freopen ( "dictionary.in" , "r" , stdin ) ;
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 12 ms 8416 KB Output is correct
8 Correct 12 ms 8260 KB Output is correct
9 Correct 11 ms 8352 KB Output is correct
10 Correct 11 ms 8236 KB Output is correct
11 Correct 10 ms 8272 KB Output is correct
12 Correct 12 ms 8172 KB Output is correct
13 Correct 14 ms 8208 KB Output is correct
14 Correct 11 ms 8264 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -