Submission #376161

#	Time	Username	Problem	Language	Result	Execution time	Memory
376161		jass921026	Lamps (JOI19_lamps)	C++14	4 / 100	48 ms	5968 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<int,int> pii;
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
const int MAXN=1E6+10, INF=1E9;
int dp[2][2][3];
bool a[MAXN], b[MAXN];
int GetMV(int x, int y){
    int res=INF;
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            int tmp=dp[0][i][j];
            if(x>0&&i!=x) tmp++;
            if(y>0&&j!=y) tmp++;
            res=min(res,tmp);
        }
    }
    return res;
}
int main(){ jizz
    int n;
    cin>>n;
    string sa, sb;
    cin>>sa>>sb;
    for(int i=0;i<n;i++){
        a[i+1]=sa[i]-'0';
        b[i+1]=sb[i]-'0';
    }
    dp[0][1][0]=dp[0][0][1]=dp[0][1][1]=dp[0][0][2]=dp[0][1][2]=INF;
    for(int i=1;i<=n;i++){
        if(a[i]==b[i]) dp[1][0][0]=GetMV(0,0);
        else dp[1][0][0]=INF;
        if(a[i]!=b[i]) dp[1][1][0]=GetMV(1,0);
        else dp[1][1][0]=INF;
        if(b[i]==0) dp[1][0][1]=GetMV(0,1);
        else dp[1][0][1]=INF;
        if(b[i]==0) dp[1][1][1]=GetMV(1,1);
        else dp[1][1][1]=INF;
        if(b[i]==1) dp[1][0][2]=GetMV(0,2);
        else dp[1][0][2]=INF;
        if(b[i]==1) dp[1][1][2]=GetMV(1,2);
        else dp[1][1][2]=INF;
        for(int j=0;j<2;j++){
            for(int k=0;k<3;k++){
                dp[0][j][k]=dp[1][j][k];
            }
        }
    }
    cout<<GetMV(0,0)<<"\n";
    return 0;
}

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