제출 #1212513

#제출 시각아이디문제언어결과실행 시간메모리
1212513minhpkLamps (JOI19_lamps)C++20
4 / 100
81 ms119792 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s,s1;
int a;
int f[1000001][5];

int dp(int i,int j){
    if (i>a){
        return 0;
    }
    if (f[i][j]!=-1){
        return f[i][j];
    }
    f[i][j]=1e7;
    int res=1e7;
    if (j==1 && s1[i]=='0'){
        res= min(res,dp(i+1,1));
    }else if (s1[i]=='0'){
        res= min(res,1+dp(i+1,1));
    }

    if (s[i]==s1[i]){
        res= min(res,dp(i+1,0));
    }

    if (j==2 && s1[i]=='1'){
        res= min(res,dp(i+1,2));
    }else if (s1[i]=='1'){
        res= min(res,1+dp(i+1,2));
    }
    if (j==3 && s1[i]-'0'=='1'-s[i]){
        res= min(res,dp(i+1,3));
    }else if (s1[i]-'0'=='1'-s[i]){
        res= min(res,1+dp(i+1,3));
    }
    return f[i][j]=res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    cin >> s >> s1;
    s='#'+s;
    s1='#'+s1;
    for (int i=1;i<=a;i++){
         for (int j=0;j<=4;j++){
              f[i][j]=-1;
         }
    }
    cout << dp(1,0) << "\n";
    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...