Submission #1211612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211612		JooDdae	Lamps (JOI19_lamps)	C++20	4 / 100	18 ms	26008 KiB

lamp

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

int n, dp[1001001][2][3];
string A, B;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> A >> B;
    for(int i=0;i<=n;i++) for(int j=0;j<2;j++) fill(dp[i][j], dp[i][j]+3, n);
	dp[0][0][2] = 0;

    for(int i=1;i<=n;i++) {
        int u = B[i-1]-'0';

        for(int j=0;j<2;j++) dp[i][j][u] = min(dp[i-1][j][2]+1, dp[i-1][j][u]);
		dp[i][1][u] = min(dp[i][1][u], dp[i-1][0][2]+2);

		if(A[i-1] == B[i-1]) {
			dp[i][0][2] = min({dp[i-1][0][2], dp[i-1][1][2], dp[i][0][u]});
			dp[i][1][2] = dp[i][1][u];
		} else {
			dp[i][0][2] = dp[i][0][u];
			dp[i][1][2] = min({dp[i-1][0][2]+1, dp[i-1][1][2], dp[i][1][u]});
		}
    }

    cout << min(dp[n][0][2], dp[n][1][2]);
}

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