Submission #157008

#	Time	Username	Problem	Language	Result	Execution time	Memory
157008		combi1k1	Lamps (JOI19_lamps)	C++14	100 / 100	87 ms	28100 KiB

lamp

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e6 + 1;
const int   inf = 1e9 + 7;

int f[N][3][2];

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

    int n;  cin >> n;

    string a;   cin >> a;
    string b;   cin >> b;

    for(int i = 0 ; i < 3 ; ++i)
    for(int j = 0 ; j < 2 ; ++j)    if (i || j)
        f[0][i][j] = inf;

    for(int i = 1 ; i <= n ; ++i)   {
        int x = a[i - 1] - '0';
        int y = b[i - 1] - '0';

        for(int j = 0 ; j < 3 ; ++j)
        for(int k = 0 ; k < 2 ; ++k)    {
            int &F = f[i][j][k];
            F = inf;
            if (j == 0 && k != (x ^ y))
                continue;
            if (j == 1 && k != y)   continue;
            if (j == 2 && k == y)   continue;

            for(int t = 0 ; t < 3 ; ++t)    {
                F = min(F,f[i - 1][t][0] + (t != j && j > 0) + k);
                F = min(F,f[i - 1][t][1] + (t != j && j > 0));
            }
        }
    }

    int ans = inf;

    for(int i = 0 ; i < 3 ; ++i)
    for(int j = 0 ; j < 2 ; ++j)
        ans = min(ans,f[n][i][j]);

    cout << ans << endl;
}
/*
13
1010010010100
0000111001011
*/

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