Submission #545109

#	Time	Username	Problem	Language	Result	Execution time	Memory
545109		chonka	Lamps (JOI19_lamps)	C++98	100 / 100	48 ms	16012 KiB

lamp

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

#define MAXN 1000007

int n ;
string a , b ;

int dp[ MAXN ][ 3 ] ;

int f ( int pos , int type ) {
    int init = a[ pos ] - '0' ;
    if ( type < 2 ) { init = type ; }
    return ( init != ( b[ pos ] - '0' ) ) ;
}

void input ( ) {
    cin >> n >> a >> b ;
    a = '0' + a ;
    b = '0' + b ;
}

void solve ( ) {
    dp[ 0 ][ 0 ] = dp[ 0 ][ 1 ] = 3 * MAXN ;
    dp[ 0 ][ 2 ] = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 0 ; j < 3 ; ++ j ) {
            dp[ i ][ j ] = 3 * MAXN ;
        }
        for ( int j = 0 ; j < 3 ; ++ j ) {
            for ( int t = 0 ; t < 3 ; ++ t ) {
                int aux = dp[ i - 1 ][ j ] ;
                if ( j != t ) {
                    aux += 2 * ( t != 2 ) ;
                }
                if ( f ( i - 1 , j ) != f ( i , t ) ) { ++ aux ; }
                dp[ i ][ t ] = min ( dp[ i ][ t ] , aux ) ;
            }
        }
    }
    int ans = 3 * MAXN ;
    for ( int i = 0 ; i < 3 ; ++ i ) {
        ans = min ( ans , dp[ n ][ i ] ) ;
    }
    cout << ( ans + 1 ) / 2 << "\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: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49