oj.uz

Submission #729729

# Submission time Handle Problem Language Result Execution time Memory
729729 2023-04-24T12:24:56 Z _callmelucian Lamps (JOI19_lamps) C++14
4 / 100
 89 ms 48380 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;
ll dp[mn][2][3];
bool A[mn], B[mn];

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

ll 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++)
            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]);
        }
    }

    ll ans = LLONG_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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 78 ms 47372 KB Output is correct
8 Correct 84 ms 48336 KB Output is correct
9 Correct 89 ms 48280 KB Output is correct
10 Correct 81 ms 48376 KB Output is correct
11 Correct 80 ms 48324 KB Output is correct
12 Correct 79 ms 48380 KB Output is correct
13 Correct 85 ms 48108 KB Output is correct
14 Correct 81 ms 48336 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -