oj.uz

Submission #428016

# Submission time Handle Problem Language Result Execution time Memory
428016 2021-06-15T07:16:46 Z tengiz05 Lamps (JOI19_lamps) C++17
4 / 100
 18 ms 31672 KB 
#include <bits/stdc++.h>
int dp[2000][2000][2];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    if (n > 500) {
        std::string a, b;
        std::cin >> a >> b;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (b[i] != '1') {
                continue;
            }
            while (i + 1 < n && b[i + 1] == '1') {
                i++;
            }
            ans++;
        }
        std::cout << ans << "\n";
    } else {
        std::string a[2], b;
        std::cin >> a[0] >> b;
        a[1] = a[0];
        for (int i = 0; i < n; i++) {
            a[1][i] ^= 1;
        }
        auto cost = [&](char c, int l, int r) {
            int ans = 0;
            for (int i = l; i <= r; i++) {
                if (c != b[i]) {
                    while (i + 1 <= r && b[i + 1] != c) {
                        i++;
                    }
                    ans++;
                }
            }
            return ans;
        };
        auto xorcost = [&](int l, int r, int f) {
            int ans = 0;
            for (int i = l; i <= r; i++) {
                if (a[f][i] != b[i]) {
                    while (i + 1 <= r && b[i + 1] != a[f][i + 1]) {
                        i++;
                    }
                    ans++;
                }
            }
            return ans;
        };
        memset(dp, -1, sizeof dp);
        std::function<int(int, int, int)> calc = [&](int l, int r, int f) {
            if (l == r) {
                return int(a[f][l] != b[l]);
            }
            int &ret = dp[l][r][f];
            if (~ret) {
                return ret;
            }
            ret = 1000000;
            ret = std::min(ret, calc(l, r, f ^ 1) + 1);
            ret = std::min(ret, cost('0', l, r) + 1);
            ret = std::min(ret, cost('1', l, r) + 1);
            ret = std::min(ret, xorcost(l, r, f));
            for (int i = l; i < r; i++) {
                ret = std::min(ret, calc(l, i, f) + calc(i + 1, r, f));
            }
            return ret;
        };
        std::cout << calc(0, n - 1, 0) << "\n";
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31564 KB Output is correct
2 Correct 15 ms 31672 KB Output is correct
3 Correct 14 ms 31588 KB Output is correct
4 Correct 14 ms 31572 KB Output is correct
5 Correct 15 ms 31564 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 14 ms 31616 KB Output is correct
8 Correct 15 ms 31556 KB Output is correct
9 Correct 18 ms 31612 KB Output is correct
10 Correct 15 ms 31564 KB Output is correct
11 Correct 15 ms 31572 KB Output is correct
12 Correct 16 ms 31624 KB Output is correct
13 Incorrect 14 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 14 ms 31564 KB Output is correct
2 Correct 15 ms 31672 KB Output is correct
3 Correct 14 ms 31588 KB Output is correct
4 Correct 14 ms 31572 KB Output is correct
5 Correct 15 ms 31564 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 14 ms 31616 KB Output is correct
8 Correct 15 ms 31556 KB Output is correct
9 Correct 18 ms 31612 KB Output is correct
10 Correct 15 ms 31564 KB Output is correct
11 Correct 15 ms 31572 KB Output is correct
12 Correct 16 ms 31624 KB Output is correct
13 Incorrect 14 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 31608 KB Output is correct
2 Correct 17 ms 31632 KB Output is correct
3 Correct 14 ms 31632 KB Output is correct
4 Correct 16 ms 31564 KB Output is correct
5 Correct 14 ms 31564 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 5 ms 3008 KB Output is correct
8 Correct 6 ms 2920 KB Output is correct
9 Correct 7 ms 2924 KB Output is correct
10 Correct 6 ms 2920 KB Output is correct
11 Correct 6 ms 3080 KB Output is correct
12 Correct 5 ms 2920 KB Output is correct
13 Correct 5 ms 2920 KB Output is correct
14 Correct 6 ms 3048 KB Output is correct

Subtask #4
0 / 49.0

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