oj.uz

Submission #659924

# Submission time Handle Problem Language Result Execution time Memory
659924 2022-11-19T17:37:02 Z cristi_a Lamps (JOI19_lamps) C++17
4 / 100
 23 ms 19904 KB 
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6;
const int inf = 1e9;

int dp[nmax+5][4];
// 0 nimic
// 1 off
// 2 on
// 3 toggle

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

    int n; string a, b; cin >> n >> a >> b;
    a = " " + a; b = " " + b;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=3; j++)
            dp[i][j] = inf;
    dp[0][0] = 0;
    for(int i=1; i<=n; i++) {
        if(a[i] == '0' and b[i] == '0') {
            dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
            dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
        }
        else if(a[i] == '0' and b[i] == '1') {
            dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
            dp[i][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
        }
        else if(a[i] == '1' and b[i] == '0') {
            dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
            dp[i][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
        }
        else if(a[i] == '1' and b[i] == '1') {
            dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
            dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
        }
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 332 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 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 332 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 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 22 ms 19812 KB Output is correct
8 Correct 23 ms 19848 KB Output is correct
9 Correct 23 ms 19896 KB Output is correct
10 Correct 23 ms 19812 KB Output is correct
11 Correct 22 ms 19848 KB Output is correct
12 Correct 21 ms 19904 KB Output is correct
13 Correct 22 ms 19864 KB Output is correct
14 Correct 21 ms 19784 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 332 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 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -