oj.uz

Submission #493170

# Submission time Handle Problem Language Result Execution time Memory
493170 2021-12-10T09:24:02 Z Lukap Lamps (JOI19_lamps) C++14
4 / 100
 396 ms 41488 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;
const int INF = 1e9 + 7;

int n;
int a[MAXN], b[MAXN];
int dp[MAXN][4][2];

int dodaj (int i, int x, int y, int fx, int fy) {
    if (a[i] == b[i]) {
        if (x == 3 && fx == 0) return INF;
        if (x >= 1 && x <= 2 && x % 2 != b[i] && fx == 0) return INF;
        if (x == 0 && fx == 1) return INF;
        if (x >= 1 && x <= 2 && x % 2 == b[i] && fx == 1) return INF;
    }
    else {
        if (x >= 1 && x <= 2 && x % 2 != b[i] && fx == 0) return INF;
        if (x == 0 && fx == 0) return INF;
        if (x >= 1 && x <= 2 && x % 2 == b[i] && fx == 1) return INF;
    }

    if (fx == 0) {
        if (x == 3) return INF;
        else if (x != 0 && x != y) return 1;
        else return 0;
    }

    else {
        if (fy == 0) {
            if (x != 3) return INF;
            return 1;
        }
        else {
            if (x == 3) return 1;
            else if (x != 0 && x != y) return 1;
            else return 0;
        }
    }
}

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

    cin >> n;

    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 2; k++) dp[i][j][k] = INF;
        }
    }

    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        a[i + 1] = c - '0';
    }


    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        b[i + 1] = c - '0';
    }

    dp[0][0][0] = 0;

    for (int i = 1; i < n + 1; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 4; l++) {
                    for (int m = 0; m < 2; m++) dp[i][j][k] = min (dp[i][j][k], dp[i - 1][l][m] + dodaj (i, j, l, k, m));
                }
//                cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << "\n";
            }
        }
    }

    int rj = INF;

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 2; j++) rj = min (rj, dp[n][i][j]);
    }

    cout << rj;

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 236 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Incorrect 1 ms 316 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 332 KB Output is correct
2 Correct 0 ms 236 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Incorrect 1 ms 316 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 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 356 ms 41372 KB Output is correct
8 Correct 344 ms 41396 KB Output is correct
9 Correct 348 ms 41412 KB Output is correct
10 Correct 355 ms 41488 KB Output is correct
11 Correct 396 ms 41488 KB Output is correct
12 Correct 312 ms 41284 KB Output is correct
13 Correct 352 ms 41460 KB Output is correct
14 Correct 351 ms 41392 KB Output is correct

Subtask #4
0 / 49.0

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