oj.uz

답안 #384430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384430 2021-04-01T16:14:34 Z ogibogi2004 Lamps (JOI19_lamps) C++14
4 / 100
 209 ms 41600 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++)
		{
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 31596 KB Output is correct
2 Correct 20 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 22 ms 31596 KB Output is correct
5 Correct 20 ms 31596 KB Output is correct
6 Correct 20 ms 31596 KB Output is correct
7 Correct 20 ms 31596 KB Output is correct
8 Correct 20 ms 31596 KB Output is correct
9 Correct 20 ms 31596 KB Output is correct
10 Correct 21 ms 31724 KB Output is correct
11 Correct 21 ms 31596 KB Output is correct
12 Correct 21 ms 31596 KB Output is correct
13 Correct 23 ms 31596 KB Output is correct
14 Correct 20 ms 31596 KB Output is correct
15 Correct 20 ms 31596 KB Output is correct
16 Incorrect 20 ms 31596 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 31596 KB Output is correct
2 Correct 20 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 22 ms 31596 KB Output is correct
5 Correct 20 ms 31596 KB Output is correct
6 Correct 20 ms 31596 KB Output is correct
7 Correct 20 ms 31596 KB Output is correct
8 Correct 20 ms 31596 KB Output is correct
9 Correct 20 ms 31596 KB Output is correct
10 Correct 21 ms 31724 KB Output is correct
11 Correct 21 ms 31596 KB Output is correct
12 Correct 21 ms 31596 KB Output is correct
13 Correct 23 ms 31596 KB Output is correct
14 Correct 20 ms 31596 KB Output is correct
15 Correct 20 ms 31596 KB Output is correct
16 Incorrect 20 ms 31596 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 20 ms 31724 KB Output is correct
5 Correct 20 ms 31596 KB Output is correct
6 Correct 20 ms 31596 KB Output is correct
7 Correct 178 ms 40428 KB Output is correct
8 Correct 194 ms 41452 KB Output is correct
9 Correct 193 ms 41408 KB Output is correct
10 Correct 188 ms 41600 KB Output is correct
11 Correct 190 ms 41468 KB Output is correct
12 Correct 195 ms 41452 KB Output is correct
13 Correct 188 ms 41452 KB Output is correct
14 Correct 209 ms 41580 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 31596 KB Output is correct
2 Correct 20 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 22 ms 31596 KB Output is correct
5 Correct 20 ms 31596 KB Output is correct
6 Correct 20 ms 31596 KB Output is correct
7 Correct 20 ms 31596 KB Output is correct
8 Correct 20 ms 31596 KB Output is correct
9 Correct 20 ms 31596 KB Output is correct
10 Correct 21 ms 31724 KB Output is correct
11 Correct 21 ms 31596 KB Output is correct
12 Correct 21 ms 31596 KB Output is correct
13 Correct 23 ms 31596 KB Output is correct
14 Correct 20 ms 31596 KB Output is correct
15 Correct 20 ms 31596 KB Output is correct
16 Incorrect 20 ms 31596 KB Output isn't correct
17 Halted 0 ms 0 KB -