Submission #395894

#	Time	Username	Problem	Language	Result	Execution time	Memory
395894		Osama_Alkhodairy	Lamps (JOI19_lamps)	C++17	100 / 100	238 ms	145452 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 1000001;

int n, dp[N][2][2][2];
string a, b;

int calc(int idx, int is_off, int is_on, int is_toggle){
    int ret = a[idx];
    if(is_off) ret = 0;
    if(is_on) ret = 1;
    if(is_toggle) ret ^= 1;
    return ret;
}
int solve(int idx, int is_off, int is_on, int is_toggle){
    if(idx == n) return 0;
    int &ret = dp[idx][is_off][is_on][is_toggle];
    if(ret != -1) return ret;
    ret = (int)1e9;
    for(int x = 0 ; x < 2 ; x++){
        for(int y = 0 ; y < 2 ; y++){
            for(int z = 0 ; z < 2 ; z++){
                if(x && y) continue;
                if(calc(idx, x, y, z) == b[idx]){
                    ret = min(ret, solve(idx + 1, x, y, z) + max(0, x - is_off) + max(0, y - is_on) + max(0, z - is_toggle));
                }
            }
        }
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> a >> b;
    for(auto &i : a) i -= '0';
    for(auto &i : b) i -= '0';
    cout << solve(0, 0, 0, 0) << endl;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49