제출 #872969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872969		tvladm2009	Lamps (JOI19_lamps)	C++14	100 / 100	34 ms	27856 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 7;
const int INF = 1e9;

int dp[N][6];

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string a, b;
	cin >> n >> a >> b;
	a = "#" + a;
	b = "#" + b;
	for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= 5; ++j) {
            dp[i][j] = INF;
        }
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
        if (a[i] == b[i]) {
            dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i - 1][3], dp[i - 1][4], dp[i - 1][5]});
        } else {
            dp[i][3] = min({dp[i - 1][0] + 1, dp[i - 1][1] + 1, dp[i - 1][2] + 1, dp[i - 1][3], dp[i - 1][4], dp[i - 1][5]});
        }
        if (b[i] == '0') {
            dp[i][1] = min({dp[i - 1][0] + 1, dp[i - 1][1], dp[i - 1][2] + 1, dp[i - 1][3] + 1, dp[i - 1][4], dp[i - 1][5] + 1});
            dp[i][5] = min({dp[i - 1][0] + 2, dp[i - 1][1] + 2, dp[i - 1][2] + 1, dp[i - 1][3] + 1, dp[i - 1][4] + 1, dp[i - 1][5]});
        } else {
            dp[i][2] = min({dp[i - 1][0] + 1, dp[i - 1][1] + 1, dp[i - 1][2], dp[i - 1][3] + 1, dp[i - 1][4] + 1, dp[i - 1][5]});
            dp[i][4] = min({dp[i - 1][0] + 2, dp[i - 1][1] + 1, dp[i - 1][2] + 2, dp[i - 1][3] + 1, dp[i - 1][4], dp[i - 1][5] + 1});
        }
	}
	cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3], dp[n][4], dp[n][5]});
    return 0;
}

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