Submission #587460

#	Time	Username	Problem	Language	Result	Execution time	Memory
587460		dutinmeow	Lamps (JOI19_lamps)	C++17	100 / 100	87 ms	27980 KiB

lamp

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

const int INF = 1e9 + 7;

int main()  {
	int N;
	cin >> N;
	string A, B;
	cin >> A >> B;

	vector<array<array<int, 2>, 3>> dp(N + 1);
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 2; j++)    
			if (i != 0 || j != 0)
				dp[0][i][j] = INF;
 
	for(int i = 1 ; i <= N; ++i) {
		int x = A[i - 1] - '0';
		int y = B[i - 1] - '0';
 
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < 2; k++) {
				int &F = dp[i][j][k];
				F = INF;
				if (j == 0 && k != (x ^ y))
					continue;
				if (j == 1 && k != y)
					continue;
				if (j == 2 && k == y)
					continue;
 
				for (int t = 0; t < 3; t++) {
					F = min(F, dp[i - 1][t][0] + int(t != j && j > 0) + k);
					F = min(F, dp[i - 1][t][1] + int(t != j && j > 0));
				}
			}
		}
	}
 
	int ans = INF;
	for(int i = 0; i < 3 ; i++)
		for(int j = 0; j < 2; j++)
			ans = min(ans, dp[N][i][j]);
	cout << ans << '\n';
}

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