Submission #203649

#	Time	Username	Problem	Language	Result	Execution time	Memory
203649		theStaticMind	Lamps (JOI19_lamps)	C++14	100 / 100	139 ms	51476 KiB

lamp

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int dp[1000001][3][2];

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);

      int n;
      cin >> n;
      string A, B;
      cin >> A >> B;

      dp[0][2][0] = 0;
      dp[0][0][0] = dp[0][1][0] = 1;
      dp[0][2][1] = 1;
      dp[0][0][1] = dp[0][1][1] = 2;
      for(int q = 0; q < n; q++){

            int i = q + 1;
            int w = A[q] - '0';
            int t = B[q] - '0';

            for(int j = 0; j < 3; j++){

                  for(int a = 0; a < 2; a++){

                        dp[i][j][a] = INF;

                        for(int k = 0; k < 3; k++){

                              for(int b = 0; b < 2; b++){

                                    int c = w;
                                    if(j < 2) c = j;
                                    if(a) c = 1 - c;

                                    if(c != t) continue;

                                    int cost = 0;

                                    if(j != k && j != 2) cost++;
                                    if(a && !b) cost++;

                                    dp[i][j][a] = min(dp[i][j][a], dp[i - 1][k][b] + cost);

                              }

                        }

                  }

            }

      }

      int ans = INF;
      for(int i = 0; i < 3; i++)for(int j = 0; j < 2; j++) ans = min(ans, dp[n][i][j]);

      cout << ans;

}

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