Submission #1163381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163381		DangKhoizzzz	Lamps (JOI19_lamps)	C++20	4 / 100	25 ms	18012 KiB

lamp

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

/*
+ array size limit ???
+ special case ??? n = 1?
+ time limit ???
*/

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 1e6 + 7;


int n, mark[maxn], dp[maxn], stb[maxn], stmark[maxn];
char a[maxn], b[maxn];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    if(b[1] == '1') b[0] = '0';
    else b[0] = '1';

    for(int i = 1; i <= n; i++)
    {
        if(b[i] == b[i-1])
        {
            stb[i] = stb[i-1];
        }
        else stb[i] = i;

        if(a[i] != b[i]) mark[i] = 1;

        if(mark[i])
        {
            if(mark[i-1] == 1)
            {
                stmark[i] = stmark[i-1];
            }
            else stmark[i] = i;
        }

    }

    dp[0] = 0;

    for(int i = 1; i <= n; i++)
    {
        dp[i] = dp[i-1] + (a[i] != b[i]);

        dp[i] = min(dp[i], dp[stb[i] - 1] + 1);
        if(mark[i])
        {
            dp[i] = min(dp[i], dp[stmark[i] - 1] + 1);

            int j = stb[stb[stmark[i] - 1] - 1];

            if(j - 1 > 0)
            {
                dp[i] = min(dp[i] , dp[j-1] + 2);
            }

        }

        int j = stb[stb[i] - 1];

        if(j-1 > 0 && mark[j-1] == 1)
        {
            dp[i] = min(dp[i] , dp[j-1] + 1);
        }
    }

    //for(int i = 1; i <= n; i++) cout << dp[i] << ' ';

    cout << dp[n] << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("inp.txt" , "r" , stdin);
    //freopen("out.txt" , "w" , stdout);
    solve();
    return 0;
}

Compilation message (stderr)

lamp.cpp:16:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int INF = 1e18 + 7;
      |                 ~~~~~^~~

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