Submission #1140256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140256		xnqs	Lamps (JOI19_lamps)	C++20	100 / 100	174 ms	147324 KiB

lamp

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int x;
std::string str[2];
int dp[1000005][3][3];

int sol(int pos, int last_xor, int last_op) {
	if (pos==x) {
		return 0;
	}
	if (dp[pos][last_xor][last_op]!=-1) {
		return dp[pos][last_xor][last_op];
	}

	int& ret = (dp[pos][last_xor][last_op] = 0x3f3f3f3f);
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 3; j++) {
			int cost = 0;
			if (last_xor!=i&&i>0) {
				++cost;
			}
			if (last_op!=j&&j>0) {
				++cost;
			}

			int this_bit = ((j>0) ? (j-1) : (str[0][pos]-'0'));
			this_bit ^= i;
			if (this_bit == str[1][pos]-'0') {
				ret = std::min(ret, sol(pos+1,i,j)+cost);
			}
		}
	}

	return ret;
}

int main() {
	std::cin >> x >> str[0] >> str[1];
	memset(dp,-1,sizeof(dp));
	std::cout << sol(0,0,0) << "\n";
}

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