oj.uz

Submission #102654

# Submission time Handle Problem Language Result Execution time Memory
102654 2019-03-26T13:28:13 Z FutymyClone Lamps (JOI19_lamps) C++14
4 / 100
 49 ms 31816 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, dp[N], a[N], b[N], c[N], lstb0[N], lstb1[N], lstc1[N];
string s, t;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s >> t; b[0] = -1;
    for (int i = 0; i < n; i++) {
        a[i + 1] = s[i] - '0';
        b[i + 1] = t[i] - '0';
        c[i + 1] = a[i + 1] ^ b[i + 1];
    }

    for (int i = 1; i <= n; i++) {
        if (b[i] == 1) lstb1[i] = (b[i - 1] == 1 ? lstb1[i - 1] : i);
        else lstb0[i] = (b[i - 1] == 0 ? lstb0[i - 1] : i);
        if (c[i] == 1) lstc1[i] = (c[i - 1] == 1 ? lstc1[i - 1] : i);
    }

    memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + (a[i] == b[i] ? 0 : 1);
        if (lstb0[i]) dp[i] = min(dp[i], dp[lstb0[i] - 1] + 1);
        if (lstb1[i]) dp[i] = min(dp[i], dp[lstb1[i] - 1] + 1);
        if (lstc1[i]) dp[i] = min(dp[i], dp[lstc1[i] - 1] + 1);
    }

    //for (int i = 1; i <= n; i++) cout << dp[i] << " ";
    //cout << '\n';
    cout << dp[n];
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 5 ms 4352 KB Output is correct
4 Correct 5 ms 4224 KB Output is correct
5 Correct 6 ms 4224 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 5 ms 4352 KB Output is correct
9 Correct 5 ms 4352 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 5 ms 4224 KB Output is correct
12 Correct 5 ms 4224 KB Output is correct
13 Incorrect 6 ms 4352 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 5 ms 4352 KB Output is correct
4 Correct 5 ms 4224 KB Output is correct
5 Correct 6 ms 4224 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 5 ms 4352 KB Output is correct
9 Correct 5 ms 4352 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 5 ms 4224 KB Output is correct
12 Correct 5 ms 4224 KB Output is correct
13 Incorrect 6 ms 4352 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 5 ms 4352 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 5 ms 4352 KB Output is correct
4 Correct 6 ms 4224 KB Output is correct
5 Correct 5 ms 4324 KB Output is correct
6 Correct 6 ms 4224 KB Output is correct
7 Correct 32 ms 23880 KB Output is correct
8 Correct 39 ms 31688 KB Output is correct
9 Correct 39 ms 31816 KB Output is correct
10 Correct 48 ms 31812 KB Output is correct
11 Correct 49 ms 31692 KB Output is correct
12 Correct 37 ms 27852 KB Output is correct
13 Correct 36 ms 27212 KB Output is correct
14 Correct 39 ms 31700 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 5 ms 4352 KB Output is correct
4 Correct 5 ms 4224 KB Output is correct
5 Correct 6 ms 4224 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 5 ms 4352 KB Output is correct
9 Correct 5 ms 4352 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 5 ms 4224 KB Output is correct
12 Correct 5 ms 4224 KB Output is correct
13 Incorrect 6 ms 4352 KB Output isn't correct
14 Halted 0 ms 0 KB -