# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
173387 | ZwariowanyMarcin | Lamps (JOI19_lamps) | C++14 | 35 ms | 16040 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
const int nax = 1e6 + 111;
void mini(int &a, int b) {
a = min(a, b);
}
int n;
char a[nax];
char b[nax];
int t[nax][3];
int main() {
a[0] = b[0] = '#';
scanf("%d", &n);
scanf("%s", a + 1);
scanf("%s", b + 1);
t[0][0] = 0;
t[0][1] = n;
t[0][2] = n;
for(int i = 1; i <= n; ++i) {
t[i][0] = t[i][1] = t[i][2] = n;
// 0
mini(t[i][0], t[i - 1][0] + (a[i] != b[i] && a[i - 1] == b[i - 1]));
mini(t[i][0], t[i - 1][1] + (a[i] != b[i] && b[i - 1] == '1'));
mini(t[i][0], t[i - 1][2] + (a[i] != b[i] && b[i - 1] == '0'));
// 1
mini(t[i][1], t[i - 1][0] + 1 + (b[i] == '0' && a[i - 1] == b[i - 1]));
mini(t[i][1], t[i - 1][1] + (b[i] == '0' && b[i - 1] == '1'));
// 2
mini(t[i][2], t[i - 1][0] + 1 + (b[i] == '1' && a[i - 1] == b[i - 1]));
mini(t[i][2], t[i - 1][2] + (b[i] == '1' && b[i - 1] == '0'));
//printf("%d %d %d %d\n", i, t[i][0], t[i][1], t[i][2]);
}
printf("%d", min({t[n][0], t[n][1], t[n][2]}));
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |