Submission #384429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384429	2021-04-01T16:13:52 Z	ogibogi2004	Lamps (JOI19_lamps)	C++14	0 / 100	62 ms	8556 KB

lamp

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int dp[MAXN][2][2][2];
int a[MAXN],b[MAXN];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		a[i]=c-'0';
	}
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		b[i]=c-'0';
	}
	for(int i=0;i<MAXN;i++)
	{
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		dp[i][i1][i2][i3]=MAXN+3;
	}
	dp[0][0][0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		{
			int a1=a[i];
			if(i1)a1=1-a1;
			if(i2)a1=0;
			if(i3)a1=1;
			if(a1==b[i])
			{
				for(int j1=0;j1<2;j1++)
				for(int j2=0;j2<2;j2++)
				for(int j3=0;j3<2;j3++)
				{
					dp[i][i1][i2][i3]=min(dp[i][i1][i2][i3],dp[i-1][j1][j2][j3]+(i1==1&&j1==0)+(i2==1&&j2==0)+(i3==1&&j3==0));
				}
			}
		}
		/*cout<<i<<":\n";
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		{
			cout<<i1<<" "<<i2<<" "<<i3<<" "<<dp[i][i1][i2][i3]<<endl;
		}*/
	}
	int ans=MAXN;
	for(int i1=0;i1<2;i1++)
	for(int i2=0;i2<2;i2++)
	for(int i3=0;i3<2;i3++)
	{
		ans=min(ans,dp[n][i1][i2][i3]);
	}
	cout<<ans<<endl;
return 0;
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3436 KB	Output is correct
2	Correct	3 ms	3436 KB	Output is correct
3	Correct	3 ms	3436 KB	Output is correct
4	Correct	3 ms	3436 KB	Output is correct
5	Correct	3 ms	3436 KB	Output is correct
6	Correct	4 ms	3436 KB	Output is correct
7	Correct	3 ms	3436 KB	Output is correct
8	Correct	3 ms	3456 KB	Output is correct
9	Correct	3 ms	3436 KB	Output is correct
10	Correct	3 ms	3436 KB	Output is correct
11	Correct	3 ms	3436 KB	Output is correct
12	Correct	4 ms	3436 KB	Output is correct
13	Correct	3 ms	3436 KB	Output is correct
14	Correct	3 ms	3436 KB	Output is correct
15	Correct	3 ms	3436 KB	Output is correct
16	Incorrect	3 ms	3436 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3436 KB	Output is correct
2	Correct	3 ms	3436 KB	Output is correct
3	Correct	3 ms	3436 KB	Output is correct
4	Correct	3 ms	3436 KB	Output is correct
5	Correct	3 ms	3436 KB	Output is correct
6	Correct	4 ms	3436 KB	Output is correct
7	Correct	3 ms	3436 KB	Output is correct
8	Correct	3 ms	3456 KB	Output is correct
9	Correct	3 ms	3436 KB	Output is correct
10	Correct	3 ms	3436 KB	Output is correct
11	Correct	3 ms	3436 KB	Output is correct
12	Correct	4 ms	3436 KB	Output is correct
13	Correct	3 ms	3436 KB	Output is correct
14	Correct	3 ms	3436 KB	Output is correct
15	Correct	3 ms	3436 KB	Output is correct
16	Incorrect	3 ms	3436 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3436 KB	Output is correct
2	Correct	3 ms	3436 KB	Output is correct
3	Correct	3 ms	3436 KB	Output is correct
4	Correct	3 ms	3436 KB	Output is correct
5	Correct	3 ms	3436 KB	Output is correct
6	Correct	4 ms	3436 KB	Output is correct
7	Runtime error	62 ms	8556 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3436 KB	Output is correct
2	Correct	3 ms	3436 KB	Output is correct
3	Correct	3 ms	3436 KB	Output is correct
4	Correct	3 ms	3436 KB	Output is correct
5	Correct	3 ms	3436 KB	Output is correct
6	Correct	4 ms	3436 KB	Output is correct
7	Correct	3 ms	3436 KB	Output is correct
8	Correct	3 ms	3456 KB	Output is correct
9	Correct	3 ms	3436 KB	Output is correct
10	Correct	3 ms	3436 KB	Output is correct
11	Correct	3 ms	3436 KB	Output is correct
12	Correct	4 ms	3436 KB	Output is correct
13	Correct	3 ms	3436 KB	Output is correct
14	Correct	3 ms	3436 KB	Output is correct
15	Correct	3 ms	3436 KB	Output is correct
16	Incorrect	3 ms	3436 KB	Output isn't correct
17	Halted	0 ms	0 KB	-