Submission #1211615

#TimeUsernameProblemLanguageResultExecution timeMemory
1211615JooDdaeLamps (JOI19_lamps)C++20
100 / 100
23 ms26008 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, dp[1001001][2][3];
string A, B;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> A >> B;
  for(int i=0;i<=n;i++) for(int j=0;j<2;j++) fill(dp[i][j], dp[i][j]+3, n);
	dp[0][0][2] = 0;

  for(int i=1;i<=n;i++) {
    int u = B[i-1]-'0';

    for(int j=0;j<2;j++) dp[i][j][u] = min({dp[i-1][j][2]+1, dp[i-1][!j][!u]+j, dp[i-1][j][u]});
		
  	if(A[i-1] == B[i-1]) {
  		dp[i][0][2] = min({dp[i-1][0][2], dp[i-1][1][2], dp[i][0][u]});
  		dp[i][1][2] = dp[i][1][u];
  	} else {
  		dp[i][0][2] = dp[i][0][u];
  		dp[i][1][2] = min({dp[i-1][0][2]+1, dp[i-1][1][2], dp[i][1][u]});
  	}
  }

  cout << min(dp[n][0][2], dp[n][1][2]);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...