Submission #914497

#	Time	Username	Problem	Language	Result	Execution time	Memory
914497		boris_mihov	Lamps (JOI19_lamps)	C++17	4 / 100	187 ms	221524 KiB

lamp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF  = 1e9;

int n;
char a[MAXN];
char b[MAXN];
int dp[MAXN][3][2];
bool bl[MAXN][3][2];

int f(int idx, int started, int flip)
{
    if (idx == n + 1)
    {
        return 0;
    }

    if (bl[idx][started][flip])
    {
        return dp[idx][started][flip];
    }

    bl[idx][started][flip] = true;
    
    if (started == b[idx] - '0')
    {
        return dp[idx][started][flip] = f(idx + 1, started, flip);
    }

    if (started != 2)
    {
        return dp[idx][started][flip] = f(idx, 2, flip);
    }

    dp[idx][started][flip] = f(idx + 1, b[idx] - '0', flip) + 1;

    if (a[idx] == b[idx])
    {
        dp[idx][started][flip] = std::min(dp[idx][started][flip], f(idx + 1, 2, 0));
    } else
    {
        dp[idx][started][flip] = std::min(dp[idx][started][flip], f(idx + 1, 2, 1) + !flip);
    }

    return dp[idx][started][flip];
}

void solve()
{
    std::cout << f(1, 2, 0) << '\n';
}

void input()
{
    std::cin >> n;
    std::cin >> a + 1;
    std::cin >> b + 1;
}   

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'void input()':
lamp.cpp:62:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     std::cin >> a + 1;
      |                 ~~^~~
lamp.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     std::cin >> b + 1;
      |                 ~~^~~

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