# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
173112 | dennisstar | Lamps (JOI19_lamps) | C++11 | 199 ms | 29816 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 ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int N;
int A[1000010], B[1000010];
int cl[1000010], ci[1000010], dif[1000010];
int Dp[1000010], mn[1000010];
int main() {
scanf("%d", &N);
for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
for (int i=1, j; i<=N; i++) {
cl[i]=cl[i-1]+1;
for (j=i; j<=N; j++) {
if (B[j]!=B[i]) break;
cl[j]=cl[i];
ci[j]=i;
}
i=j-1;
}
for (int i=1, j; i<=N; i++) {
if (B[i]==A[i]) continue;
for (j=i; j<=N; j++) {
if (B[j]==A[j]) break;
dif[j]=i;
}
i=j-1;
}
int st=1;
for (st=1; st<=N; st++) if (A[st]!=B[st]) break;
if (st>N) {
puts("0"); return 0;
}
mn[st]=1-cl[st+1];
Dp[st]=1;
for (int i=st+1; i<=N; i++) {
Dp[i]=Dp[i-1]; mn[i]=mn[i-1];
if (A[i]==B[i]) continue;
Dp[i]=Dp[dif[i]-1]+1;
Dp[i]=min(Dp[i], mn[dif[i]-1]+cl[dif[i]-1]+1); mn[i]=min(mn[i], Dp[i]-cl[i+1]);
Dp[i]=min(Dp[i], Dp[ci[i]-1]+1);
}
printf("%d\n", Dp[N]);
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... |