Submission #1128224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128224		Alihan_8	Lamps (JOI19_lamps)	C++20	100 / 100	70 ms	14164 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

signed main(){
	int n; cin >> n;
	
	string a, b; cin >> a >> b;
	
	for ( int i = 0; i < n; i++ ){
		a[i] -= '0', b[i] -= '0';
	}
	
	auto op = [&](int x, int j){
		return j > 0 ? j - 1 : x;
	};
	
	vector <array<int,3>> dp(n);
	
	for ( int i = 0; i < n; i++ ){
		dp[i] = {n, n, n};
		
		for ( auto p: {0, 1, 2} ){
			for ( auto c: {0, 1, 2} ){
				int cnt = 0;
			
				if ( !i ) cnt = (c != 0);
				else cnt = dp[i - 1][p] + (p != c && c != 0);
				
				if ( (!i || op(a[i - 1], p) == b[i - 1]) && op(a[i], c) != b[i] ) cnt++;
				
				dp[i][c] = min(dp[i][c], cnt);
			}
		}
	}
	
	cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << '\n';
}

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