Submission #1211615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211615		JooDdae	Lamps (JOI19_lamps)	C++20	100 / 100	23 ms	26008 KiB

lamp

#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]);
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49