# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
110506 | AngusRitossa | Lamps (JOI19_lamps) | C++14 | 1078 ms | 23800 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>
using namespace std;
int memo[1000010][2], done[1000010][2], a[1000010], b[1000010], n, loopcost[1000010][2];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
char c;
scanf(" %c", &c);
a[i] = c-'0';
}
for (int i = 0; i < n; i++)
{
char c;
scanf(" %c", &c);
b[i] = c-'0';
}
for (int i = n-1; i >= 0; i--)
{
for (int t = 0; t < 2; t++)
{
loopcost[i][t] = 1e9;
if (a[i] == (b[i]^t))
{
memo[i][t] = memo[i+1][t];
continue;
}
int ans = memo[i+1][!t] + !t; // Remove/add a toggle, therefore curr is correct
int extracost = 1, isok = 1, istoggled = t;
if (i != n-1 && b[i+1] == b[i])
{
loopcost[i][t] = memo[i+1][t]+1;
loopcost[i][t] = min(loopcost[i][t], loopcost[i+1][t]);
}
else
{
for (int j = i; j < n; j++)
{
if ((b[j] == b[i]) != isok)
{
isok = !isok;
istoggled = !istoggled;
if (istoggled) extracost++;
}
int am = memo[j+1][istoggled]+extracost;
loopcost[i][t] = min(loopcost[i][t], am);
}
}
ans = min(ans, loopcost[i][t]);
memo[i][t] = ans;
}
}
int ans = memo[0][0];
printf("%d\n", ans);
}
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... |