oj.uz

Submission #107675

# Submission time Handle Problem Language Result Execution time Memory
107675 2019-04-25T12:24:28 Z Saboon Lamps (JOI19_lamps) C++14
4 / 100
 786 ms 259016 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;

int dp[maxn][65];

inline int mab(int fi, int se){
	return fi + se * 4;
}

inline 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;
}

inline int transfer(int q, int fi, int se){
	q = transform(q, fi);
	q = transform(q, se);
	return q;
}

inline bool C(int x){
	return x > 0;
}

int lcs[5][5];
int pd[4][4][4][4];

inline int cost(int fi, int se, int all){
	int Fi = (all / 1) % 4;
	int Se = (all / 4) % 4;
	if (pd[fi][se][Fi][Se] != -1)
		return pd[fi][se][Fi][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]));
		}
	}
	//	cout << fi << " " << se << " " << th << " ----- " << cnt - lcs[3][3] << " -----> " << Fi << " " << Se << " " << Th << endl;
	return pd[fi][se][Fi][Se] = cnt - lcs[2][2];
}

vector<int> go[2][2];

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 = 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 (int x = 0; x <= 3; x++){
				for (int y = (x > 0); y <= 3; y++){
					dp[i][it] = min(dp[i][it], dp[i - 1][mab(x, y)] + cost(x, y, it));
				}
			}
			if (i == n)
				answer = min(answer, dp[i][it]);
		}
	}
	cout << answer << endl;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 254876 KB Output is correct
2 Correct 219 ms 254972 KB Output is correct
3 Correct 213 ms 254664 KB Output is correct
4 Correct 231 ms 254800 KB Output is correct
5 Correct 212 ms 254684 KB Output is correct
6 Correct 211 ms 254752 KB Output is correct
7 Correct 199 ms 254712 KB Output is correct
8 Correct 212 ms 254736 KB Output is correct
9 Correct 208 ms 254756 KB Output is correct
10 Correct 219 ms 254768 KB Output is correct
11 Correct 236 ms 254756 KB Output is correct
12 Correct 204 ms 254716 KB Output is correct
13 Correct 252 ms 254712 KB Output is correct
14 Correct 202 ms 254712 KB Output is correct
15 Correct 200 ms 254752 KB Output is correct
16 Correct 198 ms 254832 KB Output is correct
17 Correct 201 ms 254768 KB Output is correct
18 Correct 204 ms 254804 KB Output is correct
19 Incorrect 206 ms 254884 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 254876 KB Output is correct
2 Correct 219 ms 254972 KB Output is correct
3 Correct 213 ms 254664 KB Output is correct
4 Correct 231 ms 254800 KB Output is correct
5 Correct 212 ms 254684 KB Output is correct
6 Correct 211 ms 254752 KB Output is correct
7 Correct 199 ms 254712 KB Output is correct
8 Correct 212 ms 254736 KB Output is correct
9 Correct 208 ms 254756 KB Output is correct
10 Correct 219 ms 254768 KB Output is correct
11 Correct 236 ms 254756 KB Output is correct
12 Correct 204 ms 254716 KB Output is correct
13 Correct 252 ms 254712 KB Output is correct
14 Correct 202 ms 254712 KB Output is correct
15 Correct 200 ms 254752 KB Output is correct
16 Correct 198 ms 254832 KB Output is correct
17 Correct 201 ms 254768 KB Output is correct
18 Correct 204 ms 254804 KB Output is correct
19 Incorrect 206 ms 254884 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 254820 KB Output is correct
2 Correct 209 ms 254708 KB Output is correct
3 Correct 217 ms 254840 KB Output is correct
4 Correct 207 ms 254756 KB Output is correct
5 Correct 217 ms 254772 KB Output is correct
6 Correct 210 ms 254752 KB Output is correct
7 Correct 699 ms 256840 KB Output is correct
8 Correct 681 ms 258892 KB Output is correct
9 Correct 663 ms 258880 KB Output is correct
10 Correct 658 ms 258940 KB Output is correct
11 Correct 786 ms 258836 KB Output is correct
12 Correct 687 ms 258924 KB Output is correct
13 Correct 635 ms 259016 KB Output is correct
14 Correct 613 ms 258764 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 254876 KB Output is correct
2 Correct 219 ms 254972 KB Output is correct
3 Correct 213 ms 254664 KB Output is correct
4 Correct 231 ms 254800 KB Output is correct
5 Correct 212 ms 254684 KB Output is correct
6 Correct 211 ms 254752 KB Output is correct
7 Correct 199 ms 254712 KB Output is correct
8 Correct 212 ms 254736 KB Output is correct
9 Correct 208 ms 254756 KB Output is correct
10 Correct 219 ms 254768 KB Output is correct
11 Correct 236 ms 254756 KB Output is correct
12 Correct 204 ms 254716 KB Output is correct
13 Correct 252 ms 254712 KB Output is correct
14 Correct 202 ms 254712 KB Output is correct
15 Correct 200 ms 254752 KB Output is correct
16 Correct 198 ms 254832 KB Output is correct
17 Correct 201 ms 254768 KB Output is correct
18 Correct 204 ms 254804 KB Output is correct
19 Incorrect 206 ms 254884 KB Output isn't correct
20 Halted 0 ms 0 KB -