oj.uz

Submission #107653

# Submission time Handle Problem Language Result Execution time Memory
107653 2019-04-25T11:54:35 Z Saboon Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 253000 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;

int dp[maxn][4][4][4];

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

char transfer(char s, int fi, int se, int th){
	int q = (int)(s - '0');
	q = transform(q, fi);
	q = transform(q, se);
	q = transform(q, th);
	return (char)(q + '0');
}

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

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

int cost(int fi, int se, int th, int Fi, int Se, int Th){
	if (pd[fi][se][th][Fi][Se][Th] != -1)
		return pd[fi][se][th][Fi][Se][Th];
	vector<int> a = {fi, se, th};
	vector<int> b = {Fi, Se, Th};
	int cnt = C(Fi) + C(Se) + C(Th);
	for (int i = 1; i <= 3; i++){
		for (int j = 1; j <= 3; 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][th][Fi][Se][Th] = cnt - lcs[3][3];
}

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][0] = 0;
	int answer = n;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= 3; j++){
			for (int k = max(0, j); k <= 3; k++){
				for (int p = max(0, k); p <= 3; p++){
					char nex = transfer(s[i - 1], j, k, p);
					if (nex != t[i - 1])
						continue;
					for (int x = 0; x <= 3; x++){
						for (int y = max(0, x); y <= 3; y++){
							for (int z = max(0, y); z <= 3; z++){
								dp[i][j][k][p] = min(dp[i][j][k][p], dp[i - 1][x][y][z] + cost(x, y, z, j, k, p));
							}
						}
					}
					if (i == n)
						answer = min(answer, dp[i][j][k][p]);
				}
			}
		}
	}
	cout << answer << endl;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 251000 KB Output is correct
2 Correct 187 ms 251000 KB Output is correct
3 Correct 191 ms 250872 KB Output is correct
4 Correct 191 ms 251096 KB Output is correct
5 Correct 205 ms 250844 KB Output is correct
6 Correct 188 ms 250836 KB Output is correct
7 Correct 206 ms 250908 KB Output is correct
8 Correct 210 ms 250888 KB Output is correct
9 Correct 204 ms 250916 KB Output is correct
10 Correct 206 ms 250928 KB Output is correct
11 Correct 216 ms 250928 KB Output is correct
12 Correct 203 ms 250872 KB Output is correct
13 Correct 206 ms 250900 KB Output is correct
14 Correct 191 ms 250904 KB Output is correct
15 Correct 188 ms 250872 KB Output is correct
16 Correct 187 ms 250864 KB Output is correct
17 Correct 196 ms 250844 KB Output is correct
18 Correct 192 ms 251000 KB Output is correct
19 Correct 195 ms 251000 KB Output is correct
20 Correct 210 ms 250872 KB Output is correct
21 Correct 203 ms 250872 KB Output is correct
22 Correct 256 ms 250876 KB Output is correct
23 Correct 209 ms 251000 KB Output is correct
24 Correct 201 ms 250892 KB Output is correct
25 Correct 200 ms 250948 KB Output is correct
26 Correct 195 ms 250928 KB Output is correct
27 Correct 190 ms 250872 KB Output is correct
28 Correct 186 ms 250872 KB Output is correct
29 Correct 186 ms 250872 KB Output is correct
30 Incorrect 200 ms 250948 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 251000 KB Output is correct
2 Correct 187 ms 251000 KB Output is correct
3 Correct 191 ms 250872 KB Output is correct
4 Correct 191 ms 251096 KB Output is correct
5 Correct 205 ms 250844 KB Output is correct
6 Correct 188 ms 250836 KB Output is correct
7 Correct 206 ms 250908 KB Output is correct
8 Correct 210 ms 250888 KB Output is correct
9 Correct 204 ms 250916 KB Output is correct
10 Correct 206 ms 250928 KB Output is correct
11 Correct 216 ms 250928 KB Output is correct
12 Correct 203 ms 250872 KB Output is correct
13 Correct 206 ms 250900 KB Output is correct
14 Correct 191 ms 250904 KB Output is correct
15 Correct 188 ms 250872 KB Output is correct
16 Correct 187 ms 250864 KB Output is correct
17 Correct 196 ms 250844 KB Output is correct
18 Correct 192 ms 251000 KB Output is correct
19 Correct 195 ms 251000 KB Output is correct
20 Correct 210 ms 250872 KB Output is correct
21 Correct 203 ms 250872 KB Output is correct
22 Correct 256 ms 250876 KB Output is correct
23 Correct 209 ms 251000 KB Output is correct
24 Correct 201 ms 250892 KB Output is correct
25 Correct 200 ms 250948 KB Output is correct
26 Correct 195 ms 250928 KB Output is correct
27 Correct 190 ms 250872 KB Output is correct
28 Correct 186 ms 250872 KB Output is correct
29 Correct 186 ms 250872 KB Output is correct
30 Incorrect 200 ms 250948 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 250912 KB Output is correct
2 Correct 205 ms 250872 KB Output is correct
3 Correct 217 ms 250928 KB Output is correct
4 Correct 209 ms 250944 KB Output is correct
5 Correct 213 ms 250920 KB Output is correct
6 Correct 225 ms 250872 KB Output is correct
7 Execution timed out 1092 ms 253000 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 251000 KB Output is correct
2 Correct 187 ms 251000 KB Output is correct
3 Correct 191 ms 250872 KB Output is correct
4 Correct 191 ms 251096 KB Output is correct
5 Correct 205 ms 250844 KB Output is correct
6 Correct 188 ms 250836 KB Output is correct
7 Correct 206 ms 250908 KB Output is correct
8 Correct 210 ms 250888 KB Output is correct
9 Correct 204 ms 250916 KB Output is correct
10 Correct 206 ms 250928 KB Output is correct
11 Correct 216 ms 250928 KB Output is correct
12 Correct 203 ms 250872 KB Output is correct
13 Correct 206 ms 250900 KB Output is correct
14 Correct 191 ms 250904 KB Output is correct
15 Correct 188 ms 250872 KB Output is correct
16 Correct 187 ms 250864 KB Output is correct
17 Correct 196 ms 250844 KB Output is correct
18 Correct 192 ms 251000 KB Output is correct
19 Correct 195 ms 251000 KB Output is correct
20 Correct 210 ms 250872 KB Output is correct
21 Correct 203 ms 250872 KB Output is correct
22 Correct 256 ms 250876 KB Output is correct
23 Correct 209 ms 251000 KB Output is correct
24 Correct 201 ms 250892 KB Output is correct
25 Correct 200 ms 250948 KB Output is correct
26 Correct 195 ms 250928 KB Output is correct
27 Correct 190 ms 250872 KB Output is correct
28 Correct 186 ms 250872 KB Output is correct
29 Correct 186 ms 250872 KB Output is correct
30 Incorrect 200 ms 250948 KB Output isn't correct
31 Halted 0 ms 0 KB -