답안 #129130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129130	2019-07-11T17:46:43 Z	mohammedehab2002	Lamps (JOI19_lamps)	C++11	4 / 100	216 ms	65120 KB

lamp

#include <iostream>
using namespace std;
int dp[4][4][1000005];
int main()
{
	int n;
	string a,b;
	cin >> n >> a >> b;
	for (int j=0;j<4;j++)
	{
		for (int k=0;k<4;k++)
		dp[j][k][0]=1e9;
	}
	dp[3][3][0]=0;
	for (int i=0;i<=n;i++)
	{
		int mn=1e9,md[4];
		for (int j=0;j<4;j++)
		md[j]=1e9;
		for (int j=0;j<4;j++)
		{
			for (int k=0;k<4;k++)
			{
				dp[j][k][i+1]=1e9;
				mn=min(mn,dp[j][k][i]);
				md[j]=min(md[j],dp[j][k][i]);
				md[k]=min(md[k],dp[j][k][i]);
			}
		}
		if (i==n)
		{
			printf("%d",mn);
			return 0;
		}
		if (a[i]==b[i])
		dp[3][3][i+1]=mn;
		else
		dp[2][3][i+1]=min(min(mn+1,md[2]),dp[2][3][i]);
		bool cur=b[i]-'0';
		dp[!cur][2][i+1]=min(min(md[!cur]+1,md[2]+1),min(dp[!cur][2][i],mn+2));
		dp[2][cur][i+1]=min(min(md[2]+1,md[cur]+1),min(dp[2][cur][i],mn+2));
		dp[cur][3][i+1]=min(min(md[cur]+1,md[3]+1),min(dp[cur][3][i],mn+2));
	}
}

Subtask #1

0 / 6.0

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

Subtask #2

0 / 41.0

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

Subtask #3

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	214 ms	65028 KB	Output is correct
8	Correct	213 ms	65044 KB	Output is correct
9	Correct	212 ms	65120 KB	Output is correct
10	Correct	213 ms	65000 KB	Output is correct
11	Correct	216 ms	65096 KB	Output is correct
12	Correct	215 ms	65028 KB	Output is correct
13	Correct	216 ms	65068 KB	Output is correct
14	Correct	216 ms	65024 KB	Output is correct

Subtask #4

0 / 49.0

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