Submission #943359

#	Time	Username	Problem	Language	Result	Execution time	Memory
943359		maxFedorchuk	Lamps (JOI19_lamps)	C++17	100 / 100	50 ms	37840 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

const long long MX=1e6+10;

int nw1[2][2]={{0,1},{0,0}};
int nw2[3][3]={{0,1,0},{1,0,0},{1,1,0}};
int dp[MX][3][2];
int ans[MX];

int a[MX];
int b[MX];

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin>>n;

    string oa,ob;
    cin>>oa>>ob;

    for(int i=1;i<=n;i++)
    {
        a[i]=(oa[i-1]-'0');
        b[i]=(ob[i-1]-'0');
    }

    for(int i=0;i<=n;i++)
    {
        ans[i]=MX;
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<2;k++)
            {
                dp[i][j][k]=MX;
            }
        }
    }

    dp[0][2][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<2;k++)
            {
                if((((j==2)?a[i]:j)^k)!=b[i])
                {
                    continue;
                }

                for(int mnj=0;mnj<3;mnj++)
                {
                    for(int mnk=0;mnk<2;mnk++)
                    {
                        dp[i][j][k]=min(dp[i][j][k],dp[i-1][mnj][mnk]+nw1[mnk][k]+nw2[mnj][j]);
                        ans[i]=min(ans[i],dp[i][j][k]);
                    }
                }
            }
        }
    }

    cout<<ans[n]<<"\n";
    return 0;
}

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