Submission #1023339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023339		NintsiChkhaidze	Lamps (JOI19_lamps)	C++17	100 / 100	358 ms	200180 KiB

lamp

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

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