Submission #106069

#	Time	Username	Problem	Language	Result	Execution time	Memory
106069		Alexa2001	Lamps (JOI19_lamps)	C++17	100 / 100	93 ms	28032 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 5;

static void min_to(int &x, int y) { if(x>y) x=y; }

int dp[Nmax][6], app[2][6], go[6][6];

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(0);

    int n, i, j, k;
    string A, B;

    cin >> n;
    cin >> A >> B;

    for(auto &it : A) it -= '0';
    for(auto &it : B) it -= '0';

    for(i=0; i<6; ++i)
        for(j=0; j<6; ++j)
            go[i][j] = (i/3 == 1 && j/3 == 0) + (i%3 != 2 && j%3 != i%3);

    for(i=0; i<2; ++i)
        for(j=0; j<6; ++j)
            app[i][j] = (j%3 == 2 ? i : j%3) ^ (j/3);

    for(i=0; i<=n; ++i)
        for(j=0; j<6; ++j)
            dp[i][j] = 1e9;

    dp[0][2] = 0;

    for(i=0; i<n; ++i)
        for(k=0; k<6; ++k)
            if(app[A[i]][k] == B[i])
                for(j=0; j<6; ++j)
                    min_to(dp[i+1][k], dp[i][j] + go[j][k]);

    int ans = 1e9;
    for(i=0; i<6; ++i) min_to(ans, dp[n][i] + go[i][2]);

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:42:24: warning: array subscript has type 'char' [-Wchar-subscripts]
             if(app[A[i]][k] == B[i])
                        ^

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