Submission #107662

#	Time	Username	Problem	Language	Result	Execution time	Memory
107662		Saboon	Lamps (JOI19_lamps)	C++14	47 / 100	1048 ms	256972 KiB

lamp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;

int dp[maxn][65];

int mab(int fi, int se, int th){
	return fi + se * 4 + 16 * th;
}

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;
}

int transfer(int q, int fi, int se, int th){
	q = transform(q, fi);
	q = transform(q, se);
	q = transform(q, th);
	return q;
}

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

int lcs[5][5];
int pd[5][5][5][5][5][5];

int cost(int fi, int se, int th, int all){
	int Fi = (all / 1) % 4;
	int Se = (all / 4) % 4;
	int Th = (all / 16) % 4;
	if (pd[fi][se][th][Fi][Se][Th] != -1)
		return pd[fi][se][th][Fi][Se][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 pd[fi][se][th][Fi][Se][Th] = cnt - lcs[3][3];
}

vector<int> go[2][2];

int main(){
	ios_base::sync_with_stdio(false);
	memset(pd, -1, sizeof pd);
	int n;
	string s, t;
	cin >> n >> s >> t;
	memset(dp, 63, sizeof dp);
	dp[0][0] = 0;
	int answer = n;
	for (int i = 0; i <= 3; i++){
		for (int j = 0; j <= 3; j++){
			for (int k = 0; k <= 3; k++){
				int nex = transfer(0, i, j, k);
				go[0][nex].push_back(mab(i, j, k));

				nex = transfer(1, i, j, k);
				go[1][nex].push_back(mab(i, j, k));
			}
		}
	}

	for (int i = 1; i <= n; i++){
		int me = (int)(s[i - 1] - '0');
		int nex = (int)(t[i - 1] - '0');
		for (auto it : go[me][nex]){
			for (int x = 0; x <= 3; x++){
				for (int y = 0; y <= 3; y++){
					for (int z = 0; z <= 3; z++){
						dp[i][it] = min(dp[i][it], dp[i - 1][mab(x, y, z)] + cost(x, y, z, it));
					}
				}
			}
			if (i == n)
				answer = min(answer, dp[i][it]);
		}
	}
	cout << answer << endl;
}

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