Submission #1003935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003935		Hanksburger	Lamps (JOI19_lamps)	C++17	100 / 100	32 ms	16304 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
int dp[1000005][3];
int apply(char x, int y)
{
    return (y==0?'0':(y==1?'1':x));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s, t;
    cin >> n >> s >> t;
    dp[0][0]=dp[0][1]=1e9;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<3; j++)
        {
            dp[i][j]=1e9;
            for (int k=0; k<3; k++)
            {
                int x=0;
                if (j!=k && j!=2)
                    x++;
                if ((i==1 || apply(s[i-2], k)==t[i-2]) && apply(s[i-1], j)!=t[i-1])
                    x++;
                dp[i][j]=min(dp[i][j], dp[i-1][k]+x);
            }
        }
    }
    cout << min(min(dp[n][0], dp[n][1]), dp[n][2]);
}

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