Submission #364697

#	Time	Username	Problem	Language	Result	Execution time	Memory
364697		Nima_Naderi	Lamps (JOI19_lamps)	C++14	100 / 100	75 ms	50196 KiB

lamp

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e6 + 5;
const ll INF = 1e15;
ll n;
ll dp[MXN][3][2];
string s, t;
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> s >> t;
    s = "$" + s, t = "$" + t;
    dp[0][0][0] = 0;
    dp[0][0][1] = 1;
    dp[0][1][0] = 1;
    dp[0][1][1] = 2;
    dp[0][2][0] = 1;
    dp[0][2][1] = 2;
    for(int i = 1; i <= n; i ++){
        dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = INF;
        dp[i][1][1] = dp[i][2][0] = dp[i][2][1] = INF;
        bool f = (s[i] == t[i]);
        if(s[i] == t[i]){
            dp[i][0][0] = min({dp[i - 1][0][0], dp[i - 1][0][1], dp[i - 1][1][0],
                               dp[i - 1][1][1], dp[i - 1][2][0], dp[i - 1][2][1]});
        }
        else{
            dp[i][0][1] = min({dp[i - 1][0][0] + 1, dp[i - 1][0][1] + 0, dp[i - 1][1][0] + 1,
                               dp[i - 1][1][1] + 0, dp[i - 1][2][0] + 1, dp[i - 1][2][1] + 0});
        }
        f = (t[i] == '1');
        if(f){
            dp[i][2][0] = min({dp[i - 1][0][0] + 1, dp[i - 1][0][1] + 1, dp[i - 1][1][0] + 1,
                               dp[i - 1][1][1] + 1, dp[i - 1][2][0] + 0, dp[i - 1][2][1] + 0});
            dp[i][1][1] = min({dp[i - 1][0][0] + 2, dp[i - 1][0][1] + 1, dp[i - 1][1][0] + 1,
                               dp[i - 1][1][1] + 0, dp[i - 1][2][0] + 2, dp[i - 1][2][1] + 1});
        }
        else{
            dp[i][1][0] = min({dp[i - 1][0][0] + 1, dp[i - 1][0][1] + 1, dp[i - 1][1][0] + 0,
                               dp[i - 1][1][1] + 0, dp[i - 1][2][0] + 1, dp[i - 1][2][1] + 1});
            dp[i][2][1] = min({dp[i - 1][0][0] + 2, dp[i - 1][0][1] + 1, dp[i - 1][1][0] + 2,
                               dp[i - 1][1][1] + 1, dp[i - 1][2][0] + 1, dp[i - 1][2][1] + 0});
        }
    }
    ll ans = min({dp[n][0][0], dp[n][0][1], dp[n][1][0],
                  dp[n][1][1], dp[n][2][0], dp[n][2][1]});
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49