#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define DBGRUN(stmt) stmt
#define DBG1(x) cout << #x << ": " << (x) << endl
#define DBG2(x, y) cout << #x << ": " << (x) << ", " << #y << ": " << (y) << endl
#define DBG3(x, y, z) cout << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << endl
#define DBG4(w, x, y, z) cout << #w << ": " << (w) << ", " << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << endl
#define DBG_ARR(a, e) cout << #a << ": "; for (int i = 0; i < e; i++) cout << a[i] << ' '; cout << endl
#define DBG_ARR2D(a, s1, e1, s2, e2) cout << #a << ": " << endl; for (int i = s1; i < e1; i++) { for (int j = s2; j < e2; j++) cout << a[i][j] << ' '; cout << '\n'; }cout << endl
#define DBG_VEC(v) cout << #v << ": "; for (auto i : v) cout << i << ' '; cout << endl
#define DBG_HERE cout << "reached line: " << __LINE__ << endl
#else
#define DBGRUN(stmt)
#define DBG1(x)
#define DBG2(x, y)
#define DBG3(x, y, z)
#define DBG4(w, x, y, z)
#define DBG_ARR(a, e)
#define DBG_ARR2D(a, s1, e1, s2, e2)
#define DBG_VEC(v)
#define DBG_HERE
#endif
#define int long long
#define f first
#define s second
#define pii pair<int, int>
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); --(a))
#define ALLV(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
template <typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B>& a) { out << "(" << a.first << ", " << a.second << ")"; return out; }
template<typename ...Ts, size_t ...Is> ostream& println_tuple_impl(ostream& os, tuple<Ts...> tuple, index_sequence<Is...>) { static_assert(sizeof...(Is) == sizeof...(Ts), "Indices must have same number of elements as tuple types!"); static_assert(sizeof...(Ts) > 0, "Cannot insert empty tuple into stream."); auto last = sizeof...(Ts) - 1; os << "("; return ((os << get<Is>(tuple) << (Is != last ? ", " : ")\n")), ...); }
template<typename ...Ts> ostream& operator<<(ostream& os, const tuple<Ts...>& tuple) { return println_tuple_impl(os, tuple, index_sequence_for<Ts...>{}); }
int N, dp[1000010];
vector<bool> AA, BB;
string A, B;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
cin >> A >> B;
for (auto i : A) AA.push_back(i - '0');
for (auto i : B) BB.push_back(i - '0');
dp[N - 1] = !(AA[N - 1] == BB[N - 1]);
FORR(i, N - 2, 0) {
dp[i] = 1e18;
// range set
int extraOperations1 = 0, prev1 = -1;
int extraOperations0 = 0, prev0 = -1;
FOR(j, i, N) {
// try 1
if (prev1 != BB[j]) {
if (BB[j] == 0) extraOperations1++;
prev1 = BB[j];
}
// try 2
if (prev0 != BB[j]) {
if (BB[j] == 1) extraOperations0++;
prev0 = BB[j];
}
// DBG4(i, j, extraOperations0, extraOperations1);
int res = dp[j + 1] + min(extraOperations0, extraOperations1) + 1;
// DBG1(res);
dp[i] = min(dp[i], res);
}
int extraToggle = 0, prevToggle = -1, prevIdx = -2;
FOR(j, i, N) {
bool toggledPiece = !AA[j];
if (toggledPiece != BB[j]) {
if (prevToggle != BB[j] || prevIdx != j - 1) extraToggle++;
prevToggle = BB[j];
prevIdx = j;
}
// DBG3(i, j, extraToggle);
int res = dp[j + 1] + extraToggle + 1;
// DBG1(res);
dp[i] = min(dp[i], res);
}
if (A[i] == B[i]) dp[i] = min(dp[i], dp[i + 1]);
}
cout << dp[0];
}
Compilation message
lamp.cpp: In function 'int32_t main()':
lamp.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
30 | #define FORR(a, b, c) for (int(a) = (b); (a) >= (c); --(a))
| ^
lamp.cpp:55:5: note: in expansion of macro 'FORR'
55 | FORR(i, N - 2, 0) {
| ^~~~
lamp.cpp:28:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
| ^
lamp.cpp:60:9: note: in expansion of macro 'FOR'
60 | FOR(j, i, N) {
| ^~~
lamp.cpp:28:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
| ^
lamp.cpp:79:9: note: in expansion of macro 'FOR'
79 | FOR(j, i, N) {
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Execution timed out |
1064 ms |
4892 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
