oj.uz

답안 #427999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -