oj.uz

답안 #729732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
729732 2023-04-24T12:30:56 Z _callmelucian Lamps (JOI19_lamps) C++17
4 / 100
 94 ms 24768 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define NL "\n"
#define SP " "
#define fmax(a, b) a = max(a, b)
#define fmin(a, b) a = min(a, b)
#define all(v) v.begin(), v.end()

const int mn = 1e6 + 1;
int dp[mn][2][3];
bool A[mn], B[mn];

int cost1 (int a, int b) {
    if (b == 0 || a == b) return 0;
    return 1;
}

int cost2 (int a, int b) {
    if (b == 2 || a == b) return 0;
    return 1;
}

void update (int i, int j, int k) {
    for (int j2 = 0; j2 < 2; j2++) {
        for (int k2 = 0; k2 < 3; k2++) {
            if (dp[i - 1][j2][k2] == INT_MAX) continue;
            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j2][k2] + cost1(j2, j) + cost2(k2, k));
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        if (c == '1') A[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        if (c == '1') B[i] = 1;
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) dp[i][j][k] = INT_MAX;
        }
    }
    dp[0][0][2] = 0;
    for (int i = 1; i <= n; i++) {
        // xor
        if (A[i] != B[i]) {
            update(i, 1, 2);
            update(i, 1, B[i]);
        }
        else update(i, 1, B[i]);

        // not xor
        if (A[i] != B[i]) update(i, 0, B[i]);
        else {
            update(i, 0, 2);
            update(i, 0, B[i]);
        }
    }

    int ans = INT_MAX;
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 3; k++) ans = min(ans, dp[n][j][k]);
    }
    cout << ans;

    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 79 ms 23800 KB Output is correct
8 Correct 82 ms 24764 KB Output is correct
9 Correct 94 ms 24708 KB Output is correct
10 Correct 70 ms 24768 KB Output is correct
11 Correct 70 ms 24692 KB Output is correct
12 Correct 66 ms 24652 KB Output is correct
13 Correct 64 ms 24508 KB Output is correct
14 Correct 71 ms 24768 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -