답안 #107682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107682	2019-04-25T12:35:52 Z	Saboon	Lamps (JOI19_lamps)	C++14	47 / 100	1000 ms	256972 KB

lamp

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e6 + 10;
 
int dp[maxn][65];
 
int mab(int fi, int se){
	return fi + se * 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;
}
 
int transfer(int q, int fi, int se){
	q = transform(q, fi);
	q = transform(q, se);
	return q;
}
 
bool C(int x){
	return x > 0;
}
 
int lcs[5][5];
int pd[257];
 
int cost(int fi, int se, int all){
	int Fi = (all / 1) % 4;
	int Se = (all / 4) % 4;
	if (pd[fi + 4 * se + 16 * Fi + 64 * Se] != -1)
		return pd[fi + 4 * se + 16 * Fi + 64 * 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]));
		}
	}
	return pd[fi + 4 * se + 16 * Fi + 64 * 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 = 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
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	199 ms	254712 KB	Output is correct
2	Correct	194 ms	254712 KB	Output is correct
3	Correct	214 ms	254768 KB	Output is correct
4	Correct	204 ms	254712 KB	Output is correct
5	Correct	194 ms	254712 KB	Output is correct
6	Correct	213 ms	254756 KB	Output is correct
7	Correct	211 ms	254712 KB	Output is correct
8	Correct	198 ms	254896 KB	Output is correct
9	Correct	217 ms	254752 KB	Output is correct
10	Correct	221 ms	254684 KB	Output is correct
11	Correct	221 ms	254792 KB	Output is correct
12	Correct	215 ms	254712 KB	Output is correct
13	Correct	196 ms	254712 KB	Output is correct
14	Correct	199 ms	254816 KB	Output is correct
15	Correct	239 ms	254716 KB	Output is correct
16	Correct	208 ms	254760 KB	Output is correct
17	Correct	202 ms	254840 KB	Output is correct
18	Correct	206 ms	254700 KB	Output is correct
19	Correct	198 ms	254712 KB	Output is correct
20	Correct	209 ms	254712 KB	Output is correct
21	Correct	211 ms	254840 KB	Output is correct
22	Correct	220 ms	254712 KB	Output is correct
23	Correct	223 ms	254796 KB	Output is correct
24	Correct	215 ms	254712 KB	Output is correct
25	Correct	221 ms	254840 KB	Output is correct
26	Correct	236 ms	254712 KB	Output is correct
27	Correct	213 ms	254712 KB	Output is correct
28	Correct	237 ms	254712 KB	Output is correct
29	Correct	225 ms	254712 KB	Output is correct
30	Correct	227 ms	254684 KB	Output is correct
31	Correct	214 ms	254860 KB	Output is correct
32	Correct	219 ms	254732 KB	Output is correct
33	Correct	209 ms	254840 KB	Output is correct
34	Correct	194 ms	254776 KB	Output is correct

Subtask #2
41.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	199 ms	254712 KB	Output is correct
2	Correct	194 ms	254712 KB	Output is correct
3	Correct	214 ms	254768 KB	Output is correct
4	Correct	204 ms	254712 KB	Output is correct
5	Correct	194 ms	254712 KB	Output is correct
6	Correct	213 ms	254756 KB	Output is correct
7	Correct	211 ms	254712 KB	Output is correct
8	Correct	198 ms	254896 KB	Output is correct
9	Correct	217 ms	254752 KB	Output is correct
10	Correct	221 ms	254684 KB	Output is correct
11	Correct	221 ms	254792 KB	Output is correct
12	Correct	215 ms	254712 KB	Output is correct
13	Correct	196 ms	254712 KB	Output is correct
14	Correct	199 ms	254816 KB	Output is correct
15	Correct	239 ms	254716 KB	Output is correct
16	Correct	208 ms	254760 KB	Output is correct
17	Correct	202 ms	254840 KB	Output is correct
18	Correct	206 ms	254700 KB	Output is correct
19	Correct	198 ms	254712 KB	Output is correct
20	Correct	209 ms	254712 KB	Output is correct
21	Correct	211 ms	254840 KB	Output is correct
22	Correct	220 ms	254712 KB	Output is correct
23	Correct	223 ms	254796 KB	Output is correct
24	Correct	215 ms	254712 KB	Output is correct
25	Correct	221 ms	254840 KB	Output is correct
26	Correct	236 ms	254712 KB	Output is correct
27	Correct	213 ms	254712 KB	Output is correct
28	Correct	237 ms	254712 KB	Output is correct
29	Correct	225 ms	254712 KB	Output is correct
30	Correct	227 ms	254684 KB	Output is correct
31	Correct	214 ms	254860 KB	Output is correct
32	Correct	219 ms	254732 KB	Output is correct
33	Correct	209 ms	254840 KB	Output is correct
34	Correct	194 ms	254776 KB	Output is correct
35	Correct	217 ms	254696 KB	Output is correct
36	Correct	214 ms	254840 KB	Output is correct
37	Correct	205 ms	254796 KB	Output is correct
38	Correct	241 ms	254840 KB	Output is correct
39	Correct	201 ms	254712 KB	Output is correct
40	Correct	234 ms	254872 KB	Output is correct
41	Correct	204 ms	254808 KB	Output is correct
42	Correct	218 ms	254856 KB	Output is correct
43	Correct	211 ms	254840 KB	Output is correct
44	Correct	195 ms	254800 KB	Output is correct
45	Correct	221 ms	254840 KB	Output is correct
46	Correct	215 ms	254832 KB	Output is correct
47	Correct	218 ms	254712 KB	Output is correct
48	Correct	211 ms	254840 KB	Output is correct
49	Correct	203 ms	254880 KB	Output is correct
50	Correct	214 ms	254840 KB	Output is correct
51	Correct	208 ms	254684 KB	Output is correct
52	Correct	219 ms	254948 KB	Output is correct
53	Correct	210 ms	254840 KB	Output is correct
54	Correct	224 ms	254832 KB	Output is correct
55	Correct	265 ms	254712 KB	Output is correct
56	Correct	209 ms	254712 KB	Output is correct
57	Correct	197 ms	254932 KB	Output is correct
58	Correct	201 ms	254692 KB	Output is correct

Subtask #3
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	226 ms	254724 KB	Output is correct
2	Correct	213 ms	254840 KB	Output is correct
3	Correct	215 ms	254712 KB	Output is correct
4	Correct	206 ms	254820 KB	Output is correct
5	Correct	214 ms	254840 KB	Output is correct
6	Correct	205 ms	254908 KB	Output is correct
7	Execution timed out	1097 ms	256972 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #4
0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	199 ms	254712 KB	Output is correct
2	Correct	194 ms	254712 KB	Output is correct
3	Correct	214 ms	254768 KB	Output is correct
4	Correct	204 ms	254712 KB	Output is correct
5	Correct	194 ms	254712 KB	Output is correct
6	Correct	213 ms	254756 KB	Output is correct
7	Correct	211 ms	254712 KB	Output is correct
8	Correct	198 ms	254896 KB	Output is correct
9	Correct	217 ms	254752 KB	Output is correct
10	Correct	221 ms	254684 KB	Output is correct
11	Correct	221 ms	254792 KB	Output is correct
12	Correct	215 ms	254712 KB	Output is correct
13	Correct	196 ms	254712 KB	Output is correct
14	Correct	199 ms	254816 KB	Output is correct
15	Correct	239 ms	254716 KB	Output is correct
16	Correct	208 ms	254760 KB	Output is correct
17	Correct	202 ms	254840 KB	Output is correct
18	Correct	206 ms	254700 KB	Output is correct
19	Correct	198 ms	254712 KB	Output is correct
20	Correct	209 ms	254712 KB	Output is correct
21	Correct	211 ms	254840 KB	Output is correct
22	Correct	220 ms	254712 KB	Output is correct
23	Correct	223 ms	254796 KB	Output is correct
24	Correct	215 ms	254712 KB	Output is correct
25	Correct	221 ms	254840 KB	Output is correct
26	Correct	236 ms	254712 KB	Output is correct
27	Correct	213 ms	254712 KB	Output is correct
28	Correct	237 ms	254712 KB	Output is correct
29	Correct	225 ms	254712 KB	Output is correct
30	Correct	227 ms	254684 KB	Output is correct
31	Correct	214 ms	254860 KB	Output is correct
32	Correct	219 ms	254732 KB	Output is correct
33	Correct	209 ms	254840 KB	Output is correct
34	Correct	194 ms	254776 KB	Output is correct
35	Correct	217 ms	254696 KB	Output is correct
36	Correct	214 ms	254840 KB	Output is correct
37	Correct	205 ms	254796 KB	Output is correct
38	Correct	241 ms	254840 KB	Output is correct
39	Correct	201 ms	254712 KB	Output is correct
40	Correct	234 ms	254872 KB	Output is correct
41	Correct	204 ms	254808 KB	Output is correct
42	Correct	218 ms	254856 KB	Output is correct
43	Correct	211 ms	254840 KB	Output is correct
44	Correct	195 ms	254800 KB	Output is correct
45	Correct	221 ms	254840 KB	Output is correct
46	Correct	215 ms	254832 KB	Output is correct
47	Correct	218 ms	254712 KB	Output is correct
48	Correct	211 ms	254840 KB	Output is correct
49	Correct	203 ms	254880 KB	Output is correct
50	Correct	214 ms	254840 KB	Output is correct
51	Correct	208 ms	254684 KB	Output is correct
52	Correct	219 ms	254948 KB	Output is correct
53	Correct	210 ms	254840 KB	Output is correct
54	Correct	224 ms	254832 KB	Output is correct
55	Correct	265 ms	254712 KB	Output is correct
56	Correct	209 ms	254712 KB	Output is correct
57	Correct	197 ms	254932 KB	Output is correct
58	Correct	201 ms	254692 KB	Output is correct
59	Correct	226 ms	254724 KB	Output is correct
60	Correct	213 ms	254840 KB	Output is correct
61	Correct	215 ms	254712 KB	Output is correct
62	Correct	206 ms	254820 KB	Output is correct
63	Correct	214 ms	254840 KB	Output is correct
64	Correct	205 ms	254908 KB	Output is correct
65	Execution timed out	1097 ms	256972 KB	Time limit exceeded
66	Halted	0 ms	0 KB	-

답안 #107682

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