제출 #1182838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182838		Gray	Lamps (JOI19_lamps)	C++20	100 / 100	195 ms	198096 KiB

lamp

#include <bits/stdc++.h>
#include <string>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

void solve(){
    ll n; cin >> n; string a, b; cin >> a >> b;
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(3, vector<ll>(2, INF)));
    dp[0][0][0]=(a[0]==b[0]?0:INF); dp[0][0][1]=(a[0]!=b[0]?1:INF);
    dp[0][1][0]=('1'==b[0]?1:INF); dp[0][1][1]=('0'==b[0]?2:INF);
    dp[0][2][0]=('0'==b[0]?1:INF); dp[0][2][1]=('1'==b[0]?2:INF);
    for (ll i=1; i<n; i++){
        if (a[i]==b[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]
        });
        if (a[i]!=b[i]) dp[i][0][1]=min({
            dp[i-1][0][1], dp[i-1][1][1], dp[i-1][2][1],
            dp[i-1][0][0]+1, dp[i-1][1][0]+1, dp[i-1][2][0]+1
        });
        if ('1'==b[i]) dp[i][1][0]=min({
            dp[i-1][0][1]+1, dp[i-1][1][1], dp[i-1][2][1]+1,
            dp[i-1][0][0]+1, dp[i-1][1][0], dp[i-1][2][0]+1
        });
        if ('0'==b[i]) dp[i][1][1]=min({
            dp[i-1][0][1]+1, dp[i-1][1][1], dp[i-1][2][1]+1,
            dp[i-1][0][0]+2, dp[i-1][1][0]+1, dp[i-1][2][0]+2
        });
        if ('0'==b[i]) dp[i][2][0]=min({
            dp[i-1][0][1]+1, dp[i-1][1][1]+1, dp[i-1][2][1],
            dp[i-1][0][0]+1, dp[i-1][1][0]+1, dp[i-1][2][0]
        });
        if ('1'==b[i]) dp[i][2][1]=min({
            dp[i-1][0][1]+1, dp[i-1][1][1]+1, dp[i-1][2][1],
            dp[i-1][0][0]+2, dp[i-1][1][0]+2, dp[i-1][2][0]+1
        });
    }
    cout << min({
        dp[n-1][0][1], dp[n-1][1][1], dp[n-1][2][1],
        dp[n-1][0][0], dp[n-1][1][0], dp[n-1][2][0]
    }) << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll c=1; c<=t; c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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