Submission #107685

#	Time	Username	Problem	Language	Result	Execution time	Memory
107685		Saboon	Lamps (JOI19_lamps)	C++14	100 / 100	554 ms	259148 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[257];
 
int cost(int fi, int se, int Fi, int Se){
	if (pd[fi + 4 * se + 16 * Fi + 64 * Se] != -1)
		return pd[fi + 4 * se + 16 * Fi + 64 * 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]));
		}
	}
	return pd[fi + 4 * se + 16 * Fi + 64 * Se] = cnt - lcs[2][2];
}
 
vector<int> go[2][2]; 
vector<pair<int,int> > vec[65];

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 = 0; i <= 3; i++)
		for (int j = 0; j <= 3; j++)
			for (int x = 0; x <= 3; x++)
				for (int y = 0; y <= 3; y++)
					vec[mab(i, j)].push_back({mab(x, y), cost(x, y, 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 (auto to : vec[it])
				dp[i][it] = min(dp[i][it], dp[i - 1][to.first] + to.second);
	}
	for (int i = 0; i < 65; i++)
		answer = min(answer, dp[n][i]);
	cout << answer << endl;
}

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