제출 #1182876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182876		Warinchai	Lamps (JOI19_lamps)	C++20	100 / 100	81 ms	26008 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
int dp[1000005][3][2];
int inf=1e9;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    string a,b;cin>>a>>b;
    for(int i=0;i<=n;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)dp[i][j][k]=inf;
    dp[0][2][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int l=0;l<2;l++)for(int m=0;m<2;m++){
            int cur=a[i];
            cur=a[i-1]-'0';
            if(k!=2)cur=k;
            if(m)cur^=1;
            if(cur!=b[i-1]-'0')continue;
            int cost=(j!=k&&k!=2)+(m>l);
            dp[i][k][m]=min(dp[i][k][m],dp[i-1][j][l]+cost);
            //if(dp[i-1][j][l]+cost<inf)cerr<<"from"<<i-1<<","<<j<<" "<<l<<" to: "<<k<<" "<<m<<":"<<dp[i-1][j][l]+cost<<"\n";
        }
    }
    int ans=inf;
    for(int j=0;j<3;j++)for(int k=0;k<2;k++)ans=min(ans,dp[n][j][k]);
    cout<<ans;
}

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