Submission #107671

#	Time	Username	Problem	Language	Result	Execution time	Memory
107671		Saboon	Lamps (JOI19_lamps)	C++14	47 / 100	1104 ms	256816 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){
	return fi + se * 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;
}

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

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

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

int cost(int fi, int se, int all){
	int Fi = (all / 1) % 4;
	int Se = (all / 4) % 4;
	if (pd[fi][se][Fi][Se] != -1)
		return pd[fi][se][Fi][Se];
	vector<int> a = {fi, se};
	vector<int> b = {Fi, Se};
	int cnt = C(Fi) + C(Se);
	for (int i = 1; i <= 2; i++){
		for (int j = 1; j <= 2; 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][Fi][Se] = cnt - lcs[2][2];
}

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++){
			int nex = transfer(0, i, j);
			go[0][nex].push_back(mab(i, j));

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

	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++){
					dp[i][it] = min(dp[i][it], dp[i - 1][mab(x, y)] + cost(x, y, 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