제출 #1362828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362828		anteknne	Lamps (JOI19_lamps)	C++20	100 / 100	37 ms	25840 KiB

lamp

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 1000 * 1000 + 17;
string a, b, b2;
int dp[MAXN][3][2];

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

    int n;
    cin >> n >> a >> b;

    a = "#" + a;
    b = "#" + b;

    for (int i = 0; i <= n; i ++) {
        for (int j = 0; j < 3; j ++) {
            for (int k = 0; k < 2; k ++) {
                dp[i][j][k] = MAXN;
            }
        }
    }

    dp[0][0][0] = 0;

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < 3; j ++) {
            for (int k = 0; k < 2; k ++) {
                int x = int(a[i]) - int('0');
                if (j == 1) {
                    x = 0;
                }
                if (j == 2) {
                    x = 1;
                }
                if (k == 1) {
                    x ^= 1;
                }
                if (x == (int(b[i]) - int('0'))) {
                    for (int j2 = 0; j2 < 3; j2 ++) {
                        for (int k2 = 0; k2 < 2; k2 ++) {
                            int c = 0;
                            if (j != 0 && j2 != j) {
                                c ++;
                            }
                            if (k != 0 && k2 != k) {
                                c ++;
                            }
                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j2][k2] + c);
                        }
                    }
                }
            }
        }
    }

    int w = MAXN;
    for (int i = 0; i < 3; i ++) {
        for (int j = 0; j < 2; j ++) {
            w = min(w, dp[n][i][j]);
        }
    }

    cout << w << "\n";

    return 0;
}

• 서브태스크 1: 6 / 6
• 서브태스크 2: 41 / 41
• 서브태스크 3: 4 / 4
• 서브태스크 4: 49 / 49