Submission #312468

#	Time	Username	Problem	Language	Result	Execution time	Memory
312468		LucaDantas	Lamps (JOI19_lamps)	C++17	4 / 100	13 ms	4508 KiB

lamp

#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e6+10;

bool mark[maxn];

string a, b;

int dp[3], new_dp[3];

// 0 -> melhor com fim branco
// 1 -> fim preto
// 2 -> fim sem fazer nd

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	cin >> a >> b;
	dp[0] = dp[1] = 0x3f3f3f3f;
	for(int i = 0; i < n; i++) {
		new_dp[0] = min(dp[0], min(dp[2],dp[1]) + 1) + (b[i]=='0' && (i==0||b[i-1]=='1'));
		new_dp[1] = min(dp[1], min(dp[2],dp[0]) + 1) + (b[i]=='1' && (i==0||b[i-1]=='0'));
		new_dp[2] = dp[2] + (a[i]!=b[i]&&(i==0||a[i-1]==b[i-1]));
		// dp[2]++;
		if((a[i]!=b[i]&&(i==0||a[i-1]==b[i-1])) || a[i] == b[i])
			new_dp[2] = min(new_dp[2], min(dp[0], dp[1]) + (a[i] != b[i]));
		swap(dp[0], new_dp[0]);
		swap(dp[1], new_dp[1]);
		swap(dp[2], new_dp[2]);
		// printf("%d: %d %d %d\n", i, dp[0], dp[1], dp[2]);
	}
	printf("%d\n", min({dp[0], dp[1], dp[2]}));
}

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