Submission #107650

#	Time	Username	Problem	Language	Result	Execution time	Memory
107650		Saboon	Lamps (JOI19_lamps)	C++14	47 / 100	1108 ms	254796 KiB

lamp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;

int dp[maxn][4][4][4];

int transform(int x, int query){
	if (query == 0)
		return x;
	else if (query == 1)
		return 0;
	else if (query == 2)
		return 1;
	else
		return 1 ^ x;
}

char transfer(char s, int fi, int se, int th){
	int q = (int)(s - '0');
	q = transform(q, fi);
	q = transform(q, se);
	q = transform(q, th);
	return (char)(q + '0');
}

bool C(int x){
	return x > 0;
}

int lcs[5][5];

int cost(int fi, int se, int th, int Fi, int Se, int Th){
	vector<int> a = {fi, se, th};
	vector<int> b = {Fi, Se, Th};
	int cnt = C(Fi) + C(Se) + C(Th);
	for (int i = 1; i <= 3; i++){
		for (int j = 1; j <= 3; j++){
			lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
			if (a[i - 1] == 0 or b[i - 1] == 0)
				continue;
			lcs[i][j] = max(lcs[i][j], (lcs[i - 1][j - 1] + 1) * (a[i - 1] == b[j - 1]));
		}
	}
//	cout << fi << " " << se << " " << th << " ----- " << cnt - lcs[3][3] << " -----> " << Fi << " " << Se << " " << Th << endl;
	return cnt - lcs[3][3];
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	string s, t;
	cin >> n >> s >> t;
	memset(dp, 63, sizeof dp);
	dp[0][0][0][0] = 0;
	int answer = n;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= 3; j++){
			for (int k = 0; k <= 3; k++){
				for (int p = 0; p <= 3; p++){
					char nex = transfer(s[i - 1], j, k, p);
					if (nex != t[i - 1])
						continue;
					for (int x = 0; x <= 3; x++){
						for (int y = 0; y <= 3; y++){
							for (int z = 0; z <= 3; z++){
								dp[i][j][k][p] = min(dp[i][j][k][p], dp[i - 1][x][y][z] + cost(x, y, z, j, k, p));
							}
						}
					}
					if (i == n)
						answer = min(answer, dp[i][j][k][p]);
				}
			}
		}
	}
	cout << answer << endl;
}

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