Submission #312638

#	Time	Username	Problem	Language	Result	Execution time	Memory
312638		LucaDantas	Lamps (JOI19_lamps)	C++17	4 / 100	37 ms	3996 KiB

lamp

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

constexpr int maxn = 1e6+10;

bool mark[maxn];

string a, b;

int dp[3][2], new_dp[3][2];

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

// segundo item da dp
// 0 -> termina normal
// 1 -> termina reversed

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	cin >> a >> b;
	dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = dp[2][1] = n;
	auto check = [](int i, char val) {
		return (b[i] == val && (i==0||b[i-1]!=val));
	};
	auto check2 = [](int i, char val) {
		return (b[i] == val);
	};
	auto check3 = [](int i) {
		return (a[i] != b[i] && (i==0||a[i-1]==b[i-1]));
	};
	for(int i = 0; i < n; i++) {
		new_dp[0][0] = min(dp[0][0],dp[0][1])+check(i, '1');
		new_dp[0][0] = min(new_dp[0][0], min({dp[1][0], dp[1][1], dp[2][0], dp[2][1]}) + 1 + check2(i, '1'));

      	new_dp[0][1] = dp[0][1]+check(i, '1');
		new_dp[0][1] = min(new_dp[0][1], min(dp[1][1], dp[2][1]) + 1 + check2(i, '1'));
		
      	new_dp[1][0] = min(dp[1][0],dp[1][1])+check(i, '0');
		new_dp[1][0] = min(new_dp[1][0], min({dp[0][0], dp[0][1], dp[2][0], dp[2][1]}) + 1 + check2(i, '0'));

		new_dp[1][1] = dp[1][1]+check(i, '0');
		new_dp[1][1] = min(new_dp[1][1], min(dp[0][1], dp[2][1]) + 1 + check2(i, '0'));

		if(a[i] != b[i])
			new_dp[2][0] = n; // inf
		else new_dp[2][0] = min({dp[0][0], dp[1][0], dp[2][0], dp[0][1], dp[1][1], dp[2][1]});

		if(a[i] == b[i])
			new_dp[2][1] = n; // inf
		else new_dp[2][1] = min({dp[0][0]+1, dp[1][0]+1, dp[2][0]+1, dp[0][1], dp[1][1], dp[2][1]});

		for(int x = 0; x < 3; x++) for(int y = 0; y < 2; y++) swap(new_dp[x][y], dp[x][y]);
	}
	printf("%d\n", min({dp[0][0], dp[1][0], dp[2][0], dp[0][1], dp[1][1], dp[2][1]}));
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:31:7: warning: variable 'check3' set but not used [-Wunused-but-set-variable]
   31 |  auto check3 = [](int i) {
      |       ^~~~~~

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