Submission #631902

#	Time	Username	Problem	Language	Result	Execution time	Memory
631902		radal	Lamps (JOI19_lamps)	C++17	4 / 100	17 ms	19880 KiB

lamp

#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];
}

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