제출 #1222695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222695		AlgorithmWarrior	Lamps (JOI19_lamps)	C++20	100 / 100	90 ms	14304 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

int const NMAX=1000005;
bool sir1[NMAX],sir2[NMAX];
int dp[NMAX][3];
int n;

void read(){
    cin>>n;
    int i;
    char ch;
    for(i=1;i<=n;++i){
        cin>>ch;
        sir1[i]=ch-'0';
    }
    for(i=1;i<=n;++i){
        cin>>ch;
        sir2[i]=ch-'0';
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int const INF=1e9;

int get_dp(){
    dp[1][0]=1+(sir2[1]!=0);
    dp[1][1]=1+(sir2[1]!=1);
    dp[1][2]=(sir1[1]!=sir2[1]);
    int i,j,k;
    for(i=2;i<=n;++i)
        for(j=0;j<3;++j){
            dp[i][j]=INF;
            int vj=((j==2)?sir1[i]:j);
            for(k=0;k<3;++k){
                int vk=((k==2)?sir1[i-1]:k);
                minself(dp[i][j],dp[i-1][k]+(j<2 && j!=k)+(vk==sir2[i-1] && vj!=sir2[i]));
            }
        }
    return min(min(dp[n][0],dp[n][1]),dp[n][2]);
}

int main()
{
    read();
    cout<<get_dp();
    return 0;
}

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