oj.uz

Submission #914493

# Submission time Handle Problem Language Result Execution time Memory
914493 2024-01-22T09:16:15 Z boris_mihov Lamps (JOI19_lamps) C++17
0 / 100
 1000 ms 5556 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];

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

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.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 2548 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 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 2548 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 Execution timed out 1082 ms 5556 KB Time limit exceeded
8 Halted 0 ms 0 KB -

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 2548 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Halted 0 ms 0 KB -