Submission #623643

#	Time	Username	Problem	Language	Result	Execution time	Memory
623643		Arnch	Lamps (JOI19_lamps)	C++17	0 / 100	5 ms	4644 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 = 2e3 + 10;

int cnt[N][N][2];
int dp[N][2];

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

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

	assert(n <= 2000);

	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			cnt[i][j][0] = (B[j] == '0');	
			cnt[i][j][1] = (B[j] == '1');
			
			if(i == j) continue;
			
			cnt[i][j][0] -= (B[j - 1] == '0' && B[j] == '0');	
			cnt[i][j][1] -= (B[j - 1] == '1' && B[j] == '1');

			cnt[i][j][0] += cnt[i][j - 1][0];
			cnt[i][j][1] += cnt[i][j - 1][1];
		}
	}

	memset(dp, 63, sizeof(dp));

	int pos = 0;
	if(A[0] != B[0]) pos = -1, dp[0][0] = dp[0][1] = 1;
	else dp[0][1] = 0;

	for(int i = 1; i < n; i++) {
		if(A[i] == B[i]) {
			dp[i][1] = dp[i - 1][1];
			pos = i;
			continue;
		}
		if(pos == -1) {
			dp[i][0] = dp[i][1] = 1;
			continue;
		}
		dp[i][0] = dp[pos][1] + 1;
		dp[i][1] = dp[i][0];
		for(int j = i; j >= 0; j--) {
			int val = 0;
			if(j == 0) {
				val += 1 + min(cnt[j][i][0], cnt[j][i][1]);
				dp[i][1] = min(dp[i][1], val);
				continue;
			}
			val = dp[j - 1][1];
			val += 1 + min(cnt[j][i][0], cnt[j][i][1]);
			dp[i][1] = min(dp[i][1], val);
			if(B[j] == '0') {
				if(A[j - 1] != B[j - 1]) {
					dp[i][1] = min(dp[i][1], dp[j - 1][0] + cnt[j][i][0]);
				}
			}
			else {
				if(A[j - 1] != B[j - 1]) {
					dp[i][1] = min(dp[i][1], dp[j - 1][0] + cnt[j][i][1]);
				}
			}
		}
		//wtf(i), wtf(dp[i][0]), wtf(dp[i][1]);
	//	wtf(i), wtf(pos), wtf(dp[i]), wtf(cnt[0][i][1]), wtf(cnt[0][i][0]);
	}

	cout<<dp[n - 1][1];

    return 0;
}

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