Submission #623834

#	Time	Username	Problem	Language	Result	Execution time	Memory
623834		Arnch	Lamps (JOI19_lamps)	C++17	100 / 100	78 ms	35224 KiB

lamp

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

ll dp[N][3];
int A[N], B[N];

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	string a, b; cin >>a >>b;

	for(int i = 0; i < n; i++) {
		A[i + 1] = (a[i] - '0') + 1;
		B[i + 1] = (b[i] - '0') + 1;
	}

	memset(dp, 63, sizeof(dp));
	dp[0][0] = 0;

	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < 3; k++) {
				if(j != 0 && j == k) {
					if(k == B[i - 1] && j != B[i]) {
						dp[i][j] = min(dp[i][j], dp[i - 1][k] + 2);
						continue;
					}
					dp[i][j] = min(dp[i][j], dp[i - 1][k]);
					continue;
				}
				if(j == 0) {
					if(k == 0) {
						if(A[i] != B[i] && A[i - 1] == B[i - 1]) {
							dp[i][j] = min(dp[i][j], dp[i - 1][k] + 2);
							continue;
						}
						dp[i][j] = min(dp[i][j], dp[i - 1][k]);
						continue;
					}
					if(A[i] != B[i] && B[i - 1] == k) {
						dp[i][j] = min(dp[i][j], dp[i - 1][k] + 2);
						continue;
					}
					dp[i][j] = min(dp[i][j], dp[i - 1][k]);
					continue;
				}
				if(k == 0) {
					if(A[i - 1] == B[i - 1] && j != B[i]) {
						dp[i][j] = min(dp[i][j], dp[i - 1][k] + 4);
						continue;
					}
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + 2);
					continue;
				}
				if(k == B[i - 1] && j != B[i]) {
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + 4);
					continue;
				}
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + 2);
				continue;
			}
		}
	}

	/*for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			cout<<"^^" <<i <<" " <<j <<" " <<dp[i][j] / 2 <<endl;
		}
	}*/

	ll ans = inf;
	for(int i = 0; i < 3; i++) ans = min(ans, dp[n][i]);

	cout<<ans / 2;

    return 0;
}

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