Submission #1114337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114337		yellowtoad	Lamps (JOI19_lamps)	C++17	4 / 100	62 ms	28876 KiB

lamp

#include <iostream>
using namespace std;
 
int n, dp[1000010][6]; // 4: 12, 5: 21;
string s, t;
 
int main() {
	cin >> n >> s >> t;
	for (int i = 0; i <= n; i++) for (int j = 0; j < 6; j++) dp[i][j] = 1e9;
	dp[0][0] = 0;
	s = " "+s; t = " "+t;
	for (int i = 1; i <= n; i++) {
		if (s[i] == t[i]) dp[i][0] = min(min(min(dp[i-1][0],dp[i-1][1]),min(dp[i-1][2],dp[i-1][3])),min(dp[i-1][4],dp[i-1][5]));
		if (t[i] == '0') dp[i][1] = min(min(min(dp[i-1][0]+1,dp[i-1][1]),min(dp[i-1][2]+1,dp[i-1][3]+1)),min(dp[i-1][4],dp[i-1][5]+1));
		if (t[i] == '1') dp[i][2] = min(min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2],dp[i-1][3]+1)),min(dp[i-1][4]+1,dp[i-1][5]));
		if (s[i] != t[i]) dp[i][3] = min(min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2]+1,dp[i-1][3])),min(dp[i-1][4]+1,dp[i-1][5]+1));
		if (t[i] == '1') dp[i][4] = min(min(min(dp[i-1][0]+2,dp[i-1][1]+1),min(dp[i-1][2]+2,dp[i-1][3]+2)),min(dp[i-1][4],dp[i-1][5]+2));
		if (t[i] == '0') dp[i][5] = min(min(min(dp[i-1][0]+2,dp[i-1][1]+2),min(dp[i-1][2]+1,dp[i-1][3]+2)),min(dp[i-1][4]+2,dp[i-1][5]));
	}
	cout << min(min(min(dp[n][0],dp[n][1]),min(dp[n][2],dp[n][3])),min(dp[n][4],dp[n][5])) << endl;
}

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