Submission #129113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
129113	2019-07-11T17:06:06 Z	Mahmoud_Adel	Lamps (JOI19_lamps)	C++14	4 / 100	243 ms	90604 KB

lamp

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int N = 1e6+5;
int n, dp[N][5], nxt[N];
string a, b;
void operate()
{
	int one = n, zero = n;
	for(int i=n-1; i>=0; i--)
	{
		if(b[i] == '1') one = i, nxt[i] = zero;
		else zero = i, nxt[i] = one;
	}
}
int sol(int i, int t)
{
	if(i == n) return 0;
	int &ret = dp[i][t];
	if(ret != -1) return ret;
	ret = sol(nxt[i], t)+1;
	if(t == 3)
	{
		if(a[i] == b[i]) ret = min(ret, sol(i+1, t));
		else if(b[i] == '0') ret = min(ret, min(sol(i+1, 2), sol(i+1, 0))+1);
		else ret = min(ret, min(sol(i+1, 2), sol(i+1, 1))+1);
	}
	if(t == 2)
	{
		if(a[i] == b[i]) ret = min(ret, sol(i+1, 3));
		else ret = min(ret, sol(i+1, t));
	}
	if(t == 1)
	{
		if(b[i] == '1') ret = min(ret, sol(i+1, t));
		else if(b[i] == a[i]) ret = min(ret, sol(i+1, 3));
		else ret = min(ret, min(sol(i+1, 2), sol(i+1, 0))+1);
	}
	if(!t)
	{
		if(b[i] == '0') ret = min(ret, sol(i+1, t));
		else if(a[i] == b[i]) ret = min(ret, sol(i+1, 3));
		else ret = min(ret, min(sol(i+1, 2), sol(i+1, 1))+1);
	}
	return ret;
}
int main()
{
	memset(dp, -1, sizeof dp);
	cin >> n >> a >> b;
	operate();
	cout << sol(0, 3) << endl;
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	19960 KB	Output is correct
2	Correct	18 ms	19832 KB	Output is correct
3	Correct	18 ms	19960 KB	Output is correct
4	Correct	18 ms	19960 KB	Output is correct
5	Correct	18 ms	19832 KB	Output is correct
6	Correct	18 ms	19832 KB	Output is correct
7	Correct	18 ms	19960 KB	Output is correct
8	Correct	18 ms	19832 KB	Output is correct
9	Correct	18 ms	19832 KB	Output is correct
10	Correct	18 ms	19960 KB	Output is correct
11	Correct	18 ms	19932 KB	Output is correct
12	Correct	18 ms	19932 KB	Output is correct
13	Correct	19 ms	19892 KB	Output is correct
14	Correct	19 ms	19960 KB	Output is correct
15	Correct	18 ms	19932 KB	Output is correct
16	Correct	18 ms	19960 KB	Output is correct
17	Correct	18 ms	19876 KB	Output is correct
18	Correct	18 ms	19872 KB	Output is correct
19	Correct	19 ms	19960 KB	Output is correct
20	Correct	18 ms	19960 KB	Output is correct
21	Correct	18 ms	19836 KB	Output is correct
22	Correct	18 ms	19932 KB	Output is correct
23	Correct	19 ms	20008 KB	Output is correct
24	Correct	23 ms	19832 KB	Output is correct
25	Correct	18 ms	19960 KB	Output is correct
26	Incorrect	19 ms	19960 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #2

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	19960 KB	Output is correct
2	Correct	18 ms	19832 KB	Output is correct
3	Correct	18 ms	19960 KB	Output is correct
4	Correct	18 ms	19960 KB	Output is correct
5	Correct	18 ms	19832 KB	Output is correct
6	Correct	18 ms	19832 KB	Output is correct
7	Correct	18 ms	19960 KB	Output is correct
8	Correct	18 ms	19832 KB	Output is correct
9	Correct	18 ms	19832 KB	Output is correct
10	Correct	18 ms	19960 KB	Output is correct
11	Correct	18 ms	19932 KB	Output is correct
12	Correct	18 ms	19932 KB	Output is correct
13	Correct	19 ms	19892 KB	Output is correct
14	Correct	19 ms	19960 KB	Output is correct
15	Correct	18 ms	19932 KB	Output is correct
16	Correct	18 ms	19960 KB	Output is correct
17	Correct	18 ms	19876 KB	Output is correct
18	Correct	18 ms	19872 KB	Output is correct
19	Correct	19 ms	19960 KB	Output is correct
20	Correct	18 ms	19960 KB	Output is correct
21	Correct	18 ms	19836 KB	Output is correct
22	Correct	18 ms	19932 KB	Output is correct
23	Correct	19 ms	20008 KB	Output is correct
24	Correct	23 ms	19832 KB	Output is correct
25	Correct	18 ms	19960 KB	Output is correct
26	Incorrect	19 ms	19960 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #3

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	19960 KB	Output is correct
2	Correct	18 ms	19832 KB	Output is correct
3	Correct	18 ms	19928 KB	Output is correct
4	Correct	17 ms	19832 KB	Output is correct
5	Correct	18 ms	19932 KB	Output is correct
6	Correct	18 ms	19932 KB	Output is correct
7	Correct	212 ms	88676 KB	Output is correct
8	Correct	243 ms	88832 KB	Output is correct
9	Correct	239 ms	90472 KB	Output is correct
10	Correct	240 ms	90604 KB	Output is correct
11	Correct	238 ms	90600 KB	Output is correct
12	Correct	241 ms	90468 KB	Output is correct
13	Correct	161 ms	29728 KB	Output is correct
14	Correct	163 ms	29544 KB	Output is correct

Subtask #4

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	19960 KB	Output is correct
2	Correct	18 ms	19832 KB	Output is correct
3	Correct	18 ms	19960 KB	Output is correct
4	Correct	18 ms	19960 KB	Output is correct
5	Correct	18 ms	19832 KB	Output is correct
6	Correct	18 ms	19832 KB	Output is correct
7	Correct	18 ms	19960 KB	Output is correct
8	Correct	18 ms	19832 KB	Output is correct
9	Correct	18 ms	19832 KB	Output is correct
10	Correct	18 ms	19960 KB	Output is correct
11	Correct	18 ms	19932 KB	Output is correct
12	Correct	18 ms	19932 KB	Output is correct
13	Correct	19 ms	19892 KB	Output is correct
14	Correct	19 ms	19960 KB	Output is correct
15	Correct	18 ms	19932 KB	Output is correct
16	Correct	18 ms	19960 KB	Output is correct
17	Correct	18 ms	19876 KB	Output is correct
18	Correct	18 ms	19872 KB	Output is correct
19	Correct	19 ms	19960 KB	Output is correct
20	Correct	18 ms	19960 KB	Output is correct
21	Correct	18 ms	19836 KB	Output is correct
22	Correct	18 ms	19932 KB	Output is correct
23	Correct	19 ms	20008 KB	Output is correct
24	Correct	23 ms	19832 KB	Output is correct
25	Correct	18 ms	19960 KB	Output is correct
26	Incorrect	19 ms	19960 KB	Output isn't correct
27	Halted	0 ms	0 KB	-