oj.uz

답안 #729726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
729726 2023-04-24T12:13:28 Z _callmelucian Lamps (JOI19_lamps) C++14
4 / 100
 95 ms 50252 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) {
    return a < b;
}

ll cost2 (int a, int b) {
    if (b == 2) return 0;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 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 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 95 ms 49232 KB Output is correct
8 Correct 85 ms 50252 KB Output is correct
9 Correct 80 ms 50252 KB Output is correct
10 Correct 78 ms 50220 KB Output is correct
11 Correct 76 ms 50212 KB Output is correct
12 Correct 76 ms 50168 KB Output is correct
13 Correct 75 ms 49964 KB Output is correct
14 Correct 91 ms 50212 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -