답안 #107650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107650	2019-04-25T11:51:00 Z	Saboon	Lamps (JOI19_lamps)	C++14	47 / 100	1000 ms	254796 KB

lamp

#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 cost(int fi, int se, int th, int Fi, int Se, int 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 cnt - lcs[3][3];
}

int main(){
	ios_base::sync_with_stdio(false);
	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 = 0; k <= 3; k++){
				for (int p = 0; 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 = 0; y <= 3; y++){
							for (int z = 0; 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
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	250872 KB	Output is correct
2	Correct	195 ms	250872 KB	Output is correct
3	Correct	223 ms	250768 KB	Output is correct
4	Correct	221 ms	250820 KB	Output is correct
5	Correct	213 ms	250872 KB	Output is correct
6	Correct	214 ms	250828 KB	Output is correct
7	Correct	190 ms	250872 KB	Output is correct
8	Correct	189 ms	250744 KB	Output is correct
9	Correct	209 ms	250872 KB	Output is correct
10	Correct	202 ms	250872 KB	Output is correct
11	Correct	203 ms	250872 KB	Output is correct
12	Correct	262 ms	250780 KB	Output is correct
13	Correct	201 ms	250872 KB	Output is correct
14	Correct	233 ms	250744 KB	Output is correct
15	Correct	203 ms	250804 KB	Output is correct
16	Correct	210 ms	251024 KB	Output is correct
17	Correct	213 ms	250872 KB	Output is correct
18	Correct	225 ms	250744 KB	Output is correct
19	Correct	221 ms	250744 KB	Output is correct
20	Correct	210 ms	250872 KB	Output is correct
21	Correct	205 ms	250872 KB	Output is correct
22	Correct	192 ms	250940 KB	Output is correct
23	Correct	214 ms	250836 KB	Output is correct
24	Correct	207 ms	250744 KB	Output is correct
25	Correct	188 ms	250872 KB	Output is correct
26	Correct	200 ms	250744 KB	Output is correct
27	Correct	220 ms	250872 KB	Output is correct
28	Correct	223 ms	250872 KB	Output is correct
29	Correct	210 ms	250872 KB	Output is correct
30	Correct	237 ms	250872 KB	Output is correct
31	Correct	212 ms	250872 KB	Output is correct
32	Correct	206 ms	250872 KB	Output is correct
33	Correct	201 ms	251000 KB	Output is correct
34	Correct	197 ms	250876 KB	Output is correct

Subtask #2
41.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	250872 KB	Output is correct
2	Correct	195 ms	250872 KB	Output is correct
3	Correct	223 ms	250768 KB	Output is correct
4	Correct	221 ms	250820 KB	Output is correct
5	Correct	213 ms	250872 KB	Output is correct
6	Correct	214 ms	250828 KB	Output is correct
7	Correct	190 ms	250872 KB	Output is correct
8	Correct	189 ms	250744 KB	Output is correct
9	Correct	209 ms	250872 KB	Output is correct
10	Correct	202 ms	250872 KB	Output is correct
11	Correct	203 ms	250872 KB	Output is correct
12	Correct	262 ms	250780 KB	Output is correct
13	Correct	201 ms	250872 KB	Output is correct
14	Correct	233 ms	250744 KB	Output is correct
15	Correct	203 ms	250804 KB	Output is correct
16	Correct	210 ms	251024 KB	Output is correct
17	Correct	213 ms	250872 KB	Output is correct
18	Correct	225 ms	250744 KB	Output is correct
19	Correct	221 ms	250744 KB	Output is correct
20	Correct	210 ms	250872 KB	Output is correct
21	Correct	205 ms	250872 KB	Output is correct
22	Correct	192 ms	250940 KB	Output is correct
23	Correct	214 ms	250836 KB	Output is correct
24	Correct	207 ms	250744 KB	Output is correct
25	Correct	188 ms	250872 KB	Output is correct
26	Correct	200 ms	250744 KB	Output is correct
27	Correct	220 ms	250872 KB	Output is correct
28	Correct	223 ms	250872 KB	Output is correct
29	Correct	210 ms	250872 KB	Output is correct
30	Correct	237 ms	250872 KB	Output is correct
31	Correct	212 ms	250872 KB	Output is correct
32	Correct	206 ms	250872 KB	Output is correct
33	Correct	201 ms	251000 KB	Output is correct
34	Correct	197 ms	250876 KB	Output is correct
35	Correct	585 ms	250796 KB	Output is correct
36	Correct	623 ms	250872 KB	Output is correct
37	Correct	545 ms	250872 KB	Output is correct
38	Correct	624 ms	250872 KB	Output is correct
39	Correct	648 ms	250844 KB	Output is correct
40	Correct	620 ms	250944 KB	Output is correct
41	Correct	660 ms	250872 KB	Output is correct
42	Correct	590 ms	250952 KB	Output is correct
43	Correct	574 ms	250872 KB	Output is correct
44	Correct	546 ms	250844 KB	Output is correct
45	Correct	554 ms	251000 KB	Output is correct
46	Correct	522 ms	250904 KB	Output is correct
47	Correct	516 ms	250884 KB	Output is correct
48	Correct	537 ms	250808 KB	Output is correct
49	Correct	544 ms	250872 KB	Output is correct
50	Correct	549 ms	250840 KB	Output is correct
51	Correct	535 ms	251064 KB	Output is correct
52	Correct	614 ms	250980 KB	Output is correct
53	Correct	567 ms	250872 KB	Output is correct
54	Correct	571 ms	250904 KB	Output is correct
55	Correct	576 ms	250868 KB	Output is correct
56	Correct	569 ms	250872 KB	Output is correct
57	Correct	569 ms	250932 KB	Output is correct
58	Correct	530 ms	250988 KB	Output is correct

Subtask #3
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	210 ms	250784 KB	Output is correct
2	Correct	190 ms	250872 KB	Output is correct
3	Correct	186 ms	250872 KB	Output is correct
4	Correct	192 ms	250932 KB	Output is correct
5	Correct	201 ms	250844 KB	Output is correct
6	Correct	191 ms	250844 KB	Output is correct
7	Execution timed out	1108 ms	254796 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #4
0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	250872 KB	Output is correct
2	Correct	195 ms	250872 KB	Output is correct
3	Correct	223 ms	250768 KB	Output is correct
4	Correct	221 ms	250820 KB	Output is correct
5	Correct	213 ms	250872 KB	Output is correct
6	Correct	214 ms	250828 KB	Output is correct
7	Correct	190 ms	250872 KB	Output is correct
8	Correct	189 ms	250744 KB	Output is correct
9	Correct	209 ms	250872 KB	Output is correct
10	Correct	202 ms	250872 KB	Output is correct
11	Correct	203 ms	250872 KB	Output is correct
12	Correct	262 ms	250780 KB	Output is correct
13	Correct	201 ms	250872 KB	Output is correct
14	Correct	233 ms	250744 KB	Output is correct
15	Correct	203 ms	250804 KB	Output is correct
16	Correct	210 ms	251024 KB	Output is correct
17	Correct	213 ms	250872 KB	Output is correct
18	Correct	225 ms	250744 KB	Output is correct
19	Correct	221 ms	250744 KB	Output is correct
20	Correct	210 ms	250872 KB	Output is correct
21	Correct	205 ms	250872 KB	Output is correct
22	Correct	192 ms	250940 KB	Output is correct
23	Correct	214 ms	250836 KB	Output is correct
24	Correct	207 ms	250744 KB	Output is correct
25	Correct	188 ms	250872 KB	Output is correct
26	Correct	200 ms	250744 KB	Output is correct
27	Correct	220 ms	250872 KB	Output is correct
28	Correct	223 ms	250872 KB	Output is correct
29	Correct	210 ms	250872 KB	Output is correct
30	Correct	237 ms	250872 KB	Output is correct
31	Correct	212 ms	250872 KB	Output is correct
32	Correct	206 ms	250872 KB	Output is correct
33	Correct	201 ms	251000 KB	Output is correct
34	Correct	197 ms	250876 KB	Output is correct
35	Correct	585 ms	250796 KB	Output is correct
36	Correct	623 ms	250872 KB	Output is correct
37	Correct	545 ms	250872 KB	Output is correct
38	Correct	624 ms	250872 KB	Output is correct
39	Correct	648 ms	250844 KB	Output is correct
40	Correct	620 ms	250944 KB	Output is correct
41	Correct	660 ms	250872 KB	Output is correct
42	Correct	590 ms	250952 KB	Output is correct
43	Correct	574 ms	250872 KB	Output is correct
44	Correct	546 ms	250844 KB	Output is correct
45	Correct	554 ms	251000 KB	Output is correct
46	Correct	522 ms	250904 KB	Output is correct
47	Correct	516 ms	250884 KB	Output is correct
48	Correct	537 ms	250808 KB	Output is correct
49	Correct	544 ms	250872 KB	Output is correct
50	Correct	549 ms	250840 KB	Output is correct
51	Correct	535 ms	251064 KB	Output is correct
52	Correct	614 ms	250980 KB	Output is correct
53	Correct	567 ms	250872 KB	Output is correct
54	Correct	571 ms	250904 KB	Output is correct
55	Correct	576 ms	250868 KB	Output is correct
56	Correct	569 ms	250872 KB	Output is correct
57	Correct	569 ms	250932 KB	Output is correct
58	Correct	530 ms	250988 KB	Output is correct
59	Correct	210 ms	250784 KB	Output is correct
60	Correct	190 ms	250872 KB	Output is correct
61	Correct	186 ms	250872 KB	Output is correct
62	Correct	192 ms	250932 KB	Output is correct
63	Correct	201 ms	250844 KB	Output is correct
64	Correct	191 ms	250844 KB	Output is correct
65	Execution timed out	1108 ms	254796 KB	Time limit exceeded
66	Halted	0 ms	0 KB	-

답안 #107650

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 41.0 / 41.0

Subtask #3 0 / 4.0

Subtask #4 0 / 49.0

Subtask #1
6.0 / 6.0

Subtask #2
41.0 / 41.0

Subtask #3
0 / 4.0

Subtask #4
0 / 49.0