제출 #1023339

#제출 시각아이디문제언어결과실행 시간메모리
1023339NintsiChkhaidzeLamps (JOI19_lamps)C++17
100 / 100
358 ms200180 KiB
#include <bits/stdc++.h>
#include <ostream>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;
 
const int N = 1e6 + 5,inf = 1e9;
int dp[N][5][5];

signed main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
  
  int n;
  cin>>n;

  string A;
  cin>>A;

  string B;
  cin>>B;

  A = '$' + A;
  B = '%' + B;

  for (int i = 0; i <= n; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 0; k < 4; k++)
        dp[i][j][k] = inf;

  dp[0][0][0] = 0;
  for (int i = 1; i <= n; i++){
    
    for (int j = 0; j < 4; j++){
      for (int k = 0; k < 4; k++){
        if (dp[i - 1][j][k] == inf) continue;

        for (int j1 = 0; j1 < 4; j1++){
          for (int k1 = 0; k1 < 4; k1++){
            if (!j1 && k1) continue;
            if (j1 == k1 && j1) continue;

            int val = (A[i] - '0');
            if (j1 == 1) val = 1;
            if (j1 == 2) val = 0;
            if (j1 == 3) val ^= 1;

            if (k1 == 1) val = 1;
            if (k1 == 2) val = 0;
            if (k1 == 3) val ^= 1;

            int f = (B[i] - '0');
            if (val != f) continue;

            int c = 0;
            if (j1 && k1){
              if (j1 == j && k1 == k) c = 0;
              else if (j1 == k && k1 == j) c = 1;
              else {
                if (j1 != j && j1 != k) c++;
                if (k1 != j && k1 != k) c++;
              }
            }else {
              if (j1 && j1 != k && j1 != j) ++c;
            }

            dp[i][j1][k1] = min(dp[i][j1][k1],c + dp[i - 1][j][k]);
          }
        }
      }
    }
  }

  int ans = inf;
  for (int j = 0; j < 4; j++)
    for (int k = 0; k < 4; k++)
      ans=min(ans,dp[n][j][k]);

  cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...