Submission #782946

#	Time	Username	Problem	Language	Result	Execution time	Memory
782946		Kahou	Lamps (JOI19_lamps)	C++14	100 / 100	119 ms	27872 KiB

lamp

/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 50;
const int N = 1e6 + 50;
int n, dp[N][3][2];
string A, B;

void solve() {
        cin >> n;
        cin >> A;
        cin >> B;
        for (int i = 0; i <= n; i++) {
                for (int j = 0; j < 3; j++) {
                        for (int k = 0; k < 2; k++) {
                                dp[i][j][k] = inf;
                        }
                }
        }
        dp[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
                for (int of = 0; of < 3; of++) {
                        for (int oinv = 0; oinv < 2; oinv++) {
                                for (int f = 0; f < 3; f++) {
                                        for (int inv = 0; inv < 2; inv++) {
                                                int c = A[i-1]-'0';
                                                if (f) c = f-1;
                                                if (inv) c = 1-c;
                                                if (c != B[i-1]-'0') continue;
                                                dp[i][f][inv] = min(dp[i][f][inv], dp[i-1][of][oinv] + (f && of != f) + (inv && !oinv));
                                        }
                                }
                        }
                }
        }
        int ans = inf;
        for (int f = 0; f < 3; f++) {
                for (int inv = 0; inv < 2; inv++) {
                        ans = min(ans, dp[n][f][inv]);
                }
        }
        cout << ans << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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