Submission #966229

#	Time	Username	Problem	Language	Result	Execution time	Memory
966229		tset	Lamps (JOI19_lamps)	C++14	100 / 100	105 ms	67536 KiB

lamp

#include<bits/stdc++.h>

using namespace std;

#define int long long

int dp[1000042][3][2];

const int INF = 1e18;

signed main()
{
    int N;
    string sA, sB;
    cin >> N;
    cin >> sA >> sB;
    vector<int> a(N), b(N);
    for(int i=0; i<N; i++)
    {
        a[i] = sA[i]-'0';
        b[i] = sB[i]-'0';
    }

    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][0][0] = 0;
    for(int iN = 0; iN < N; iN++)
    {
        for(int setPrec = 0; setPrec < 3; setPrec++)
        {
            for(int togglePrec = 0; togglePrec < 2; togglePrec++)
            {
                for(int setNow = 0; setNow < 3; setNow++)
                {
                    for(int toggleNow = 0; toggleNow < 2; toggleNow++)
                    {
                        int bit;
                        if(setNow == 0) bit = a[iN];
                        else bit = setNow-1;
                        
                        if(toggleNow == 1) bit = (bit +1)%2;
                        
                        if(bit == b[iN])
                        {
                            dp[iN+1][setNow][toggleNow] = min(dp[iN+1][setNow][toggleNow], dp[iN][setPrec][togglePrec] + (setNow!=setPrec && setNow != 0) + (toggleNow > togglePrec));
                        }
                    }
                }
            }
            
        }

    }
    int ans = INF;
    for(int setFin = 0; setFin < 3; setFin++)
    {
        for(int toggleFin = 0; toggleFin < 2; toggleFin++)
        {
            ans = min(ans, dp[N][setFin][toggleFin]);
        }
    }
    printf("%lld\n", ans);
}

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