oj.uz

Submission #1032962

# Submission time Handle Problem Language Result Execution time Memory
1032962 2024-07-24T11:22:06 Z juicy Lamps (JOI19_lamps) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	const int inf = 1e9 + 7;

	int N; string A, B; cin >> N >> A >> B;
	vector<array<int, 3>> dp(N + 1, {inf, inf, inf});
	auto match = [&](int i, int j) {
		char c = j == 2 ? A[i] : j + '0';
		return c == B[i]; 
	};
	dp[0][2] = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (dp[i][j] != inf) {
				for (int k = 0; k < 3; ++k) {
					int c = dp[i][j];
					c += j != k && k != 2;
					c += i == 0 || (match(i - 1, j) && !match(i, k));
					dp[i + 1][k] = min(dp[i + 1][k], c);
				}
			}
		}
	}
	cout << min({dp[N][0], dp[N][1], dp[N][2]});
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -