Submission #384799

#	Time	Username	Problem	Language	Result	Execution time	Memory
384799		kostia244	Lamps (JOI19_lamps)	C++17	100 / 100	70 ms	27980 KiB

lamp

#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: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49