oj.uz

Submission #171301

# Submission time Handle Problem Language Result Execution time Memory
171301 2019-12-28T08:58:28 Z gs18103 Lamps (JOI19_lamps) C++14
0 / 100
 9 ms 420 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 1010101;
const int INF = 1e9;
const ll LINF = 1e18;

int dp[4][MAX];

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

    int n;
    string s, t;
    cin >> n >> s >> t;
    if(s[0] != t[0]) {
        dp[0][0] = INF;
        if(t[0] == '0') dp[1][0] = 1, dp[2][0] = 2;
        if(t[0] == '1') dp[1][0] = 2, dp[2][0] = 1;
        dp[3][0] = 1;
    }
    for(int i = 1; i < n; i++) {
        if(s[i] == t[i]) {
            dp[0][i] = min({dp[0][i-1], dp[1][i-1], dp[2][i-1], dp[3][i-1]});
            if(t[i] == '0') dp[1][i] = dp[1][i-1], dp[2][i] = dp[2][i-1]+1;
            if(t[i] == '1') dp[2][i] = dp[2][i-1], dp[1][i] = dp[1][i-1]+1;
            dp[3][i] = dp[3][i-1]+1;
        }
        else {
            dp[0][i] = INF;
            if(t[i] == '0') {
                dp[1][i] = min({dp[0][i-1]+1, dp[1][i-1], dp[2][i-1]+1, dp[3][i-1]+1});
                dp[2][i] = dp[1][i] + 1;
            }
            else {
                dp[2][i] = min({dp[0][i-1]+1, dp[1][i-1]+1, dp[2][i-1], dp[3][i-1]+1});
                dp[1][i] = dp[2][i] + 1;
            }
            dp[3][i] = min({dp[0][i-1]+1, dp[1][i-1]+1, dp[2][i-1]+1, dp[3][i-1]});
        }
    }
    cout << min({dp[0][n-1], dp[1][n-1], dp[2][n-1], dp[3][n-1]});
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -