제출 #1013930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013930		vjudge1	Lamps (JOI19_lamps)	C++17	100 / 100	43 ms	41560 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n;
ll a[N], b[N], dp[N][3]; // 0 la dang thuc hien operation 0, 1 la dang thuc hien operation 1, 2 la khong lam j
void to_thic_cau(){
    cin >> n;
    for(int i = 1; i <= n;i++){
        char c; cin >> c;
        a[i] = c - '0';
    }
    for(int i = 1; i <= n;i++){
        char c; cin >> c;
        b[i] = c - '0';
    }
    for(int i = 0; i <= n;i++) dp[i][0] = dp[i][1] = dp[i][2] = inf;
    dp[1][0] = (b[1] == 1) + 1, dp[1][1] = (b[1] == 0) + 1, dp[1][2] = (a[1] != b[1]);
    for(int i = 2; i <= n;i++){
        // xet TH thuc hien operation 0
        dp[i][0] = min(dp[i][0], dp[i-1][0] + (b[i] == 1 && b[i-1] == 0));
        dp[i][0] = min(dp[i][0], dp[i-1][1] + (b[i] == 1 && b[i-1] == 1) + 1);
        dp[i][0] = min(dp[i][0], dp[i-1][2] + (b[i] == 1 && a[i-1] == b[i-1]) + 1);

        // xet TH thuc hien operation 1
        dp[i][1] = min(dp[i][1], dp[i-1][0] + (b[i] == 0 && b[i-1] == 0) + 1);
        dp[i][1] = min(dp[i][1], dp[i-1][1] + (b[i] == 0 && b[i-1] == 1));
        dp[i][1] = min(dp[i][1], dp[i-1][2] + (b[i] == 0 && a[i-1] == b[i-1]) + 1);

        // xet TH khong thuc hien j 
        dp[i][2] = min(dp[i][2], dp[i-1][0] + (a[i] != b[i] && b[i-1] == 0));
        dp[i][2] = min(dp[i][2], dp[i-1][1] + (a[i] != b[i] && b[i-1] == 1));
        dp[i][2] = min(dp[i][2], dp[i-1][2] + (a[i] != b[i] && a[i-1] == b[i-1]));
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}   

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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