Submission #914493

#	Time	Username	Problem	Language	Result	Execution time	Memory
914493		boris_mihov	Lamps (JOI19_lamps)	C++17	0 / 100	1082 ms	5556 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];

void solve()
{
    dp[n + 1][0] = dp[n + 1][1] = dp[n + 1][2] = 0;
    for (int idx = n ; idx >= 1 ; --idx)
    {
        for (int last = 0 ; last < 3 ; ++last)
        {
            int curr = 1 + a[idx] - b[idx];
            dp[idx][last] = dp[idx + 1][curr] + (curr != last && curr != 1);

            int cnt = 1;
            int newLast = last;
            for (int next = idx ; next <= n ; ++next)
            {
                curr = 1 + ((a[next] == '0' ? '1' : '0') - b[next]);
                cnt += (curr != last && curr != 1);
                newLast = curr;
                dp[idx][last] = std::min(dp[idx][last], dp[next + 1][newLast] + cnt);
            }
        }
    }

    std::cout << dp[1][1] << '\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:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     std::cin >> a + 1;
      |                 ~~^~~
lamp.cpp:45:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     std::cin >> b + 1;
      |                 ~~^~~

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