oj.uz

Submission #129126

# Submission time Handle Problem Language Result Execution time Memory
129126 2019-07-11T17:41:06 Z mohammedehab2002 Lamps (JOI19_lamps) C++11
0 / 100
 125 ms 4836 KB 
#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[i]=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^1][2][i+1]=min(min(md[cur^1]+1,md[2]+1),min(dp[cur^1][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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 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 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 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 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 504 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Runtime error 125 ms 4836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 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 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -