oj.uz

Submission #384797

# Submission time Handle Problem Language Result Execution time Memory
384797 2021-04-02T09:45:56 Z kostia244 Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 50 ms 48108 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 12;
int dp[maxn][3][2];
void minq(int &a, int b) {
    a = min(a, b);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string a, b;
    cin >> n >> a >> b;
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int lst = 0; lst < 3; lst++) {
            dp[i][lst][0] = min(dp[i][lst][0], dp[i][lst][1]);
            dp[i][lst][1] = min(dp[i][lst][1], dp[i][lst][0]+1);
            for(int rev = 0; rev < 2; rev++) {
                int cur = (a[i]-'0');
                int targ = (b[i]-'0')^rev;
                if((cur == targ && !lst) || lst-1 == targ)
                    minq(dp[i+1][lst][rev], dp[i][lst][rev]);
                if(cur == targ)
                    minq(dp[i+1][0][rev], dp[i][lst][rev]);
                minq(dp[i+1][1+targ][rev], dp[i][lst][rev]+1);
            }
        }
    }
    int ans = 69<<20;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 2; j++)
            ans = min(dp[n][i][j], ans);
    cout << ans << '\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 48108 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 48108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 48108 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -