Submission #384431

# Submission time Handle Problem Language Result Execution time Memory
384431 2021-04-01T16:15:23 Z ogibogi2004 Lamps (JOI19_lamps) C++14
4 / 100
190 ms 39680 KB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+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++)
		{
			if(i2&&i3)continue;
			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;
}
# Verdict Execution time Memory Grader output
1 Correct 20 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 19 ms 31596 KB Output is correct
4 Correct 19 ms 31596 KB Output is correct
5 Correct 23 ms 31596 KB Output is correct
6 Correct 23 ms 31596 KB Output is correct
7 Correct 19 ms 31596 KB Output is correct
8 Correct 19 ms 31596 KB Output is correct
9 Correct 20 ms 31596 KB Output is correct
10 Correct 20 ms 31596 KB Output is correct
11 Correct 20 ms 31596 KB Output is correct
12 Correct 23 ms 31596 KB Output is correct
13 Correct 20 ms 31596 KB Output is correct
14 Correct 19 ms 31596 KB Output is correct
15 Correct 19 ms 31596 KB Output is correct
16 Incorrect 19 ms 31596 KB Output isn't correct
17 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 20 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 19 ms 31596 KB Output is correct
4 Correct 19 ms 31596 KB Output is correct
5 Correct 23 ms 31596 KB Output is correct
6 Correct 23 ms 31596 KB Output is correct
7 Correct 19 ms 31596 KB Output is correct
8 Correct 19 ms 31596 KB Output is correct
9 Correct 20 ms 31596 KB Output is correct
10 Correct 20 ms 31596 KB Output is correct
11 Correct 20 ms 31596 KB Output is correct
12 Correct 23 ms 31596 KB Output is correct
13 Correct 20 ms 31596 KB Output is correct
14 Correct 19 ms 31596 KB Output is correct
15 Correct 19 ms 31596 KB Output is correct
16 Incorrect 19 ms 31596 KB Output isn't correct
17 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 22 ms 31596 KB Output is correct
2 Correct 20 ms 31596 KB Output is correct
3 Correct 19 ms 31596 KB Output is correct
4 Correct 19 ms 31596 KB Output is correct
5 Correct 22 ms 31596 KB Output is correct
6 Correct 20 ms 31596 KB Output is correct
7 Correct 190 ms 39680 KB Output is correct
8 Correct 184 ms 39532 KB Output is correct
9 Correct 184 ms 39404 KB Output is correct
10 Correct 186 ms 39532 KB Output is correct
11 Correct 184 ms 39404 KB Output is correct
12 Correct 183 ms 39404 KB Output is correct
13 Correct 184 ms 39532 KB Output is correct
14 Correct 188 ms 39404 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 20 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 19 ms 31596 KB Output is correct
4 Correct 19 ms 31596 KB Output is correct
5 Correct 23 ms 31596 KB Output is correct
6 Correct 23 ms 31596 KB Output is correct
7 Correct 19 ms 31596 KB Output is correct
8 Correct 19 ms 31596 KB Output is correct
9 Correct 20 ms 31596 KB Output is correct
10 Correct 20 ms 31596 KB Output is correct
11 Correct 20 ms 31596 KB Output is correct
12 Correct 23 ms 31596 KB Output is correct
13 Correct 20 ms 31596 KB Output is correct
14 Correct 19 ms 31596 KB Output is correct
15 Correct 19 ms 31596 KB Output is correct
16 Incorrect 19 ms 31596 KB Output isn't correct
17 Halted 0 ms 0 KB -