Submission #132762

#	Time	Username	Problem	Language	Result	Execution time	Memory
132762		SirCeness	Lamps (JOI19_lamps)	C++14	4 / 100	822 ms	143528 KiB

lamp

#include <bits/stdc++.h>

using namespace std;
//#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

int n;
string s, t;
int dp[1000006][16];

void mini(int& a, int b){
	a = min(a, b);
}

int g(int ma, int mb){
	if (ma == mb) return 0;
	if (ma == 0) return 0;
	if (ma == 1) return (mb != 4 && mb != 5 && mb != 10 && mb != 11);
	if (ma == 2) return (mb != 6 && mb != 7 && mb != 12 && mb != 13);
	if (ma == 3) return (mb != 8 && mb != 9 && mb != 14 && mb != 15);
	if (ma == 4){
		if (mb == 11) return 0;
		if (mb == 1 || mb == 5 || mb == 10) return 1;
		return 2;
	}
	if (ma == 5){
		if (mb == 10) return 0;
		if (mb == 1 || mb == 4 || mb == 11) return 1;
		return 2;
	}
	if (ma == 6){
		if (mb == 13) return 0;
		if (mb == 2 || mb == 7 || mb == 12) return 1;
		return 2;
	}
	if (ma == 7){
		if (mb == 12) return 0;
		if (mb == 2 || mb == 6 || mb == 13) return 1;
		return 2;
	}
	if (ma == 8){
		if (mb == 14) return 0;
		if (mb == 3 || mb == 9 || mb == 15) return 1;
		return 2;
	}
	if (ma == 9) {
		if (mb == 15) return 0;
		if (mb == 3 || mb == 8 || mb == 14) return 1;
		return 2;
	}
	if (ma == 10){
		if (mb == 5) return 1;
		if (mb == 1 || mb == 4 || mb == 11) return 2;
		return 3;
	}
	if (ma == 11){
		if (mb == 4) return 1;
		if (mb == 1 || mb == 5 || mb == 10) return 2;
		return 3;
	}
	if (ma == 12){
		if (mb == 7) return 1;
		if (mb == 2 || mb == 6 || mb == 13) return 2;
		return 3;
	}
	if (ma == 13){
		if (mb == 6) return 1;
		if (mb == 2 || mb == 7 || mb == 12) return 2;
		return 3; 
	}
	if (ma == 14){
		if (mb == 8) return 1;
		if (mb == 3 || mb == 8 || mb == 9 || mb == 14 || mb == 15) return 2;
		return 3;
	}
	if (ma == 15){
		if (mb == 9) return 1;
		if (mb == 3 || mb == 8 || mb == 9 || mb == 14 || mb == 15) return 2;
		return 3;
	}
	assert(0);
}

int f(int ind, int mod){
	if (ind == n) return g(mod, 0);
	if (dp[ind][mod] != -1) return dp[ind][mod];
	//cout << "f(" << ind << ", " << mod << ")" << endl;
	int ans = 10000000;
	if (s[ind] == '0' && t[ind] == '0'){
		
		mini(ans, g(mod, 0) + f(ind+1, 0));
		mini(ans, g(mod, 1) + f(ind+1, 1));
		mini(ans, g(mod, 6) + f(ind+1, 6));
		mini(ans, g(mod, 7) + f(ind+1, 7));
		mini(ans, g(mod, 9) + f(ind+1, 9));
		mini(ans, g(mod, 10) + f(ind+1, 10));
		mini(ans, g(mod, 13) + f(ind+1, 13));
		mini(ans, g(mod, 14) + f(ind+1, 14));
	} else if (s[ind] == '1' && t[ind] == '0'){
		mini(ans, g(mod, 1) + f(ind+1, 1));
		mini(ans, g(mod, 3) + f(ind+1, 3));
		mini(ans, g(mod, 6) + f(ind+1, 6));
		mini(ans, g(mod, 7) + f(ind+1, 7));
		mini(ans, g(mod, 9) + f(ind+1, 9));
		mini(ans, g(mod, 10) + f(ind+1, 10));
		mini(ans, g(mod, 13) + f(ind+1, 13));
		mini(ans, g(mod, 14) + f(ind+1, 14));
	} else if (s[ind] == '0' && t[ind] == '1'){
		mini(ans, g(mod, 2) + f(ind+1, 2));
		mini(ans, g(mod, 3) + f(ind+1, 3));
		mini(ans, g(mod, 4) + f(ind+1, 4));
		mini(ans, g(mod, 5) + f(ind+1, 5));
		mini(ans, g(mod, 8) + f(ind+1, 8));
		mini(ans, g(mod, 11) + f(ind+1, 11));
		mini(ans, g(mod, 12) + f(ind+1, 12));
		mini(ans, g(mod, 15) + f(ind+1, 15));
	} else if (s[ind] == '1' && t[ind] == '1'){
		mini(ans, g(mod, 0) + f(ind+1, 0));
		mini(ans, g(mod, 2) + f(ind+1, 2));
		mini(ans, g(mod, 4) + f(ind+1, 4));
		mini(ans, g(mod, 5) + f(ind+1, 5));
		mini(ans, g(mod, 8) + f(ind+1, 8));
		mini(ans, g(mod, 11) + f(ind+1, 11));
		mini(ans, g(mod, 12) + f(ind+1, 12));
		mini(ans, g(mod, 15) + f(ind+1, 15));
	} else assert(0);
	return dp[ind][mod] = ans;
}

int main(){
	cin >> n >> s >> t;
	//cout << s << " " << t << endl;
	//for (int i = 0; i < 16; i++) cout << bas(g(i, 1)) << endl;
	
	for (int  i = 0; i < n; i++) for (int j = 0; j < 16; j++) dp[i][j] = -1;
	
	cout << f(0, 0) << endl;
}

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