oj.uz

Submission #132762

# Submission time Handle Problem Language Result Execution time Memory
132762 2019-07-19T13:31:03 Z SirCeness Lamps (JOI19_lamps) C++14
4 / 100
 822 ms 143528 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Incorrect 2 ms 376 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Incorrect 2 ms 376 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 757 ms 143528 KB Output is correct
8 Correct 805 ms 143476 KB Output is correct
9 Correct 798 ms 143336 KB Output is correct
10 Correct 802 ms 143316 KB Output is correct
11 Correct 822 ms 143460 KB Output is correct
12 Correct 792 ms 143456 KB Output is correct
13 Correct 782 ms 143372 KB Output is correct
14 Correct 777 ms 143296 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Incorrect 2 ms 376 KB Output isn't correct
27 Halted 0 ms 0 KB -