Submission #132789

#	Time	Username	Problem	Language	Result	Execution time	Memory
132789		SirCeness	Lamps (JOI19_lamps)	C++14	100 / 100	321 ms	129876 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];
int g[6][6];

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


int f(int ind, int mod){
	if (ind == n) return 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][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));
	} else if (s[ind] == '1' && 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][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));
	} else if (s[ind] == '0' && t[ind] == '1'){
		//mini(ans, g[mod][0] + f(ind+1, 0));
		//mini(ans, g[mod][1] + f(ind+1, 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));
	} else if (s[ind] == '1' && t[ind] == '1'){
		mini(ans, g[mod][0] + f(ind+1, 0));
		//mini(ans, g[mod][1] + f(ind+1, 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));
	} 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;
	
	g[0][0] = 0; g[0][1] = 1; g[0][2] = 1; g[0][3]  = 1; g[0][4] = 2; g[0][5] = 2;
	g[1][0] = 0; g[1][1] = 0; g[1][2] = 1; g[1][3]  = 1; g[1][4] = 1; g[1][5] = 2;
	g[2][0] = 0; g[2][1] = 1; g[2][2] = 0; g[2][3]  = 1; g[2][4] = 2; g[2][5] = 1;
	g[3][0] = 0; g[3][1] = 1; g[3][2] = 1; g[3][3]  = 0; g[3][4] = 1; g[3][5] = 1;
	g[4][0] = 0; g[4][1] = 0; g[4][2] = 1; g[4][3]  = 0; g[4][4] = 0; g[4][5] = 1;
	g[5][0] = 0; g[5][1] = 1; g[5][2] = 0; g[5][3]  = 0; g[5][4] = 1; g[5][5] = 0;	
	cout << f(0, 0) << endl;
}

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