oj.uz

Submission #428757

# Submission time Handle Problem Language Result Execution time Memory
428757 2021-06-15T14:16:02 Z tengiz05 Lamps (JOI19_lamps) C++17
4 / 100
 102 ms 35576 KB 
#include <bits/stdc++.h>
constexpr int N = 1000000;
int dp[N + 1][2][2][2];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::string a, b;
    std::cin >> a >> b;
    a = "#" + a;
    b = "#" + b;
    // [pos][0][1][xor]
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a0 = 0; a0 < 2; a0++)
            for (int a1 = 0; a1 < 2; a1++)
                for (int xr = 0; xr < 2; xr++) {
                    char t = a[i];
                    if (a0) t = '0';
                    if (a1) t = '1';
                    if (xr) t ^= 1;
                    if (t != b[i]) {
                        continue;
                    }
                    int &ret = dp[i][a0][a1][xr];
                    ret = dp[i - 1][a0][a1][xr] - a0 - a1 - xr;
                    ret = std::min(ret, dp[i - 1][0][a1][xr] - a1 - xr);
                    ret = std::min(ret, dp[i - 1][a0][0][xr] - a0 - xr);
                    ret = std::min(ret, dp[i - 1][0][0][xr] - xr);
                    ret = std::min(ret, dp[i - 1][0][a1][0] - a1);
                    ret = std::min(ret, dp[i - 1][a0][0][0] - a0);
                    ret = std::min(ret, dp[i - 1][0][0][0]);
                    ret = std::min(ret, dp[i - 1][1][a1][xr] - a1 - xr);
                    ret = std::min(ret, dp[i - 1][a0][1][xr] - a0 - xr);
                    ret = std::min(ret, dp[i - 1][1][1][xr] - xr);
                    ret = std::min(ret, dp[i - 1][1][a1][1] - a1);
                    ret = std::min(ret, dp[i - 1][a0][1][1] - a0);
                    ret = std::min(ret, dp[i - 1][1][1][1]);
                    ret += a0 + a1 + xr;
                }
    }
    int ans = n;
    for (int a0 = 0; a0 < 2; a0++)
        for (int a1 = 0; a1 < 2; a1++)
            for (int xr = 0; xr < 2; xr++)
                ans = std::min(ans, dp[n][a0][a1][xr]);
    std::cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 15 ms 31612 KB Output is correct
3 Correct 15 ms 31560 KB Output is correct
4 Correct 15 ms 31564 KB Output is correct
5 Correct 15 ms 31624 KB Output is correct
6 Correct 15 ms 31556 KB Output is correct
7 Correct 15 ms 31564 KB Output is correct
8 Correct 14 ms 31540 KB Output is correct
9 Correct 16 ms 31552 KB Output is correct
10 Correct 15 ms 31564 KB Output is correct
11 Correct 15 ms 31540 KB Output is correct
12 Correct 15 ms 31616 KB Output is correct
13 Incorrect 16 ms 31564 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 15 ms 31612 KB Output is correct
3 Correct 15 ms 31560 KB Output is correct
4 Correct 15 ms 31564 KB Output is correct
5 Correct 15 ms 31624 KB Output is correct
6 Correct 15 ms 31556 KB Output is correct
7 Correct 15 ms 31564 KB Output is correct
8 Correct 14 ms 31540 KB Output is correct
9 Correct 16 ms 31552 KB Output is correct
10 Correct 15 ms 31564 KB Output is correct
11 Correct 15 ms 31540 KB Output is correct
12 Correct 15 ms 31616 KB Output is correct
13 Incorrect 16 ms 31564 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31556 KB Output is correct
2 Correct 15 ms 31564 KB Output is correct
3 Correct 15 ms 31592 KB Output is correct
4 Correct 16 ms 31584 KB Output is correct
5 Correct 15 ms 31596 KB Output is correct
6 Correct 15 ms 31564 KB Output is correct
7 Correct 102 ms 35484 KB Output is correct
8 Correct 90 ms 35408 KB Output is correct
9 Correct 92 ms 35440 KB Output is correct
10 Correct 88 ms 35480 KB Output is correct
11 Correct 89 ms 35448 KB Output is correct
12 Correct 89 ms 35576 KB Output is correct
13 Correct 94 ms 35464 KB Output is correct
14 Correct 92 ms 35452 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 15 ms 31612 KB Output is correct
3 Correct 15 ms 31560 KB Output is correct
4 Correct 15 ms 31564 KB Output is correct
5 Correct 15 ms 31624 KB Output is correct
6 Correct 15 ms 31556 KB Output is correct
7 Correct 15 ms 31564 KB Output is correct
8 Correct 14 ms 31540 KB Output is correct
9 Correct 16 ms 31552 KB Output is correct
10 Correct 15 ms 31564 KB Output is correct
11 Correct 15 ms 31540 KB Output is correct
12 Correct 15 ms 31616 KB Output is correct
13 Incorrect 16 ms 31564 KB Output isn't correct
14 Halted 0 ms 0 KB -