Submission #545094

#	Time	Username	Problem	Language	Result	Execution time	Memory
545094		chonka	Lamps (JOI19_lamps)	C++98	4 / 100	14 ms	8416 KiB

lamp

#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
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49