oj.uz

Submission #914497

# Submission time Handle Problem Language Result Execution time Memory
914497 2024-01-22T09:27:27 Z boris_mihov Lamps (JOI19_lamps) C++17
4 / 100
 187 ms 221524 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 123 ms 125680 KB Output is correct
8 Correct 173 ms 221524 KB Output is correct
9 Correct 169 ms 221520 KB Output is correct
10 Correct 179 ms 221496 KB Output is correct
11 Correct 164 ms 221360 KB Output is correct
12 Correct 187 ms 127564 KB Output is correct
13 Correct 93 ms 127572 KB Output is correct
14 Correct 91 ms 129724 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -