oj.uz

Submission #132759

# Submission time Handle Problem Language Result Execution time Memory
132759 2019-07-19T13:24:10 Z SirCeness Lamps (JOI19_lamps) C++14
4 / 100
 807 ms 145580 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, 2));
		mini(ans, g(mod, 2) + 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 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 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 777 ms 145380 KB Output is correct
8 Correct 801 ms 145404 KB Output is correct
9 Correct 807 ms 145380 KB Output is correct
10 Correct 793 ms 145580 KB Output is correct
11 Correct 805 ms 145424 KB Output is correct
12 Correct 778 ms 145440 KB Output is correct
13 Correct 774 ms 145252 KB Output is correct
14 Correct 775 ms 145356 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -