oj.uz

Submission #427999

# Submission time Handle Problem Language Result Execution time Memory
427999 2021-06-15T06:58:41 Z tengiz05 Lamps (JOI19_lamps) C++17
4 / 100
 17 ms 31620 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;
        };
        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 = 1e9;
            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);
            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 31564 KB Output is correct
3 Correct 14 ms 31564 KB Output is correct
4 Correct 17 ms 31524 KB Output is correct
5 Correct 14 ms 31600 KB Output is correct
6 Correct 14 ms 31616 KB Output is correct
7 Correct 14 ms 31564 KB Output is correct
8 Correct 16 ms 31564 KB Output is correct
9 Correct 17 ms 31508 KB Output is correct
10 Correct 14 ms 31564 KB Output is correct
11 Correct 14 ms 31588 KB Output is correct
12 Correct 16 ms 31620 KB Output is correct
13 Incorrect 14 ms 31508 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 31564 KB Output is correct
3 Correct 14 ms 31564 KB Output is correct
4 Correct 17 ms 31524 KB Output is correct
5 Correct 14 ms 31600 KB Output is correct
6 Correct 14 ms 31616 KB Output is correct
7 Correct 14 ms 31564 KB Output is correct
8 Correct 16 ms 31564 KB Output is correct
9 Correct 17 ms 31508 KB Output is correct
10 Correct 14 ms 31564 KB Output is correct
11 Correct 14 ms 31588 KB Output is correct
12 Correct 16 ms 31620 KB Output is correct
13 Incorrect 14 ms 31508 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 16 ms 31564 KB Output is correct
2 Correct 15 ms 31616 KB Output is correct
3 Correct 16 ms 31564 KB Output is correct
4 Correct 16 ms 31504 KB Output is correct
5 Correct 14 ms 31564 KB Output is correct
6 Correct 14 ms 31580 KB Output is correct
7 Correct 5 ms 2772 KB Output is correct
8 Correct 6 ms 2664 KB Output is correct
9 Correct 6 ms 2664 KB Output is correct
10 Correct 6 ms 2792 KB Output is correct
11 Correct 6 ms 2664 KB Output is correct
12 Correct 5 ms 2664 KB Output is correct
13 Correct 6 ms 2664 KB Output is correct
14 Correct 5 ms 2664 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 31564 KB Output is correct
3 Correct 14 ms 31564 KB Output is correct
4 Correct 17 ms 31524 KB Output is correct
5 Correct 14 ms 31600 KB Output is correct
6 Correct 14 ms 31616 KB Output is correct
7 Correct 14 ms 31564 KB Output is correct
8 Correct 16 ms 31564 KB Output is correct
9 Correct 17 ms 31508 KB Output is correct
10 Correct 14 ms 31564 KB Output is correct
11 Correct 14 ms 31588 KB Output is correct
12 Correct 16 ms 31620 KB Output is correct
13 Incorrect 14 ms 31508 KB Output isn't correct
14 Halted 0 ms 0 KB -