Submission #545098

#TimeUsernameProblemLanguageResultExecution timeMemory
545098chonkaLamps (JOI19_lamps)C++98
4 / 100
12 ms6344 KiB
#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_alt = 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 ] ) ;
        }
        else {
            dp[ i ] = min ( dp[ i ] , dp[ i - 1 ] + 1 ) ;
        }
        if ( i > 1 && b[ i - 1 ] != b[ i - 2 ] ) {
            ++ mn_alt ;
        }
        dp[ i ] = min ( dp[ i ] , ( mn_alt + 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 ) ;
        }
        mn_alt = min ( mn_alt , 2 * dp[ i - 1 ] + 2 ) ;
    }
    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 ;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...