제출 #631902

#제출 시각아이디문제언어결과실행 시간메모리
631902radalLamps (JOI19_lamps)C++17
4 / 100
17 ms19880 KiB
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define pb push_back
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;

constexpr int N = 1e6+10;

int dp[N],l[N][3];

int main(){
    ios_base :: sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    s = '#'+s;
    t = '#'+t;
    rep(i,1,n+1){
        if (s[i] != t[i]) l[i][2] = 1+l[i-1][2];
        else l[i][2] = 0;
        if (t[i] == '1') l[i][1] = l[i-1][1]+1;
        else l[i][0] = l[i-1][0]+1;
        if (s[i] == t[i]){
            dp[i] = dp[i-1];
            continue;
        }
        dp[i] = dp[i-max({l[i][1],l[i][0],l[i][2]})]+1;
    }
    cout << dp[n];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...