Submission #1097664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097664		ten_xd	Lamps (JOI19_lamps)	C++17	100 / 100	31 ms	28008 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 1e6+54321, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

int n,wyn;
string A,B;
int dp[N], dpS[N], dp0[N], dp1[N], dp0S[N], dp1S[N];

void solve()
{
	cin >> n >> A >> B;

	if(A[0] == B[0])
	{
		dp[0] = 0, dpS[0] = 2;
	}
	else
	{
		dp[0] = 1, dpS[0] = 1;
	}

	if(B[0] == '0')
	{
		dp0[0] = 1, dp1[0] = INF;
	}
	else
	{
		dp1[0] = 1, dp0[0] = INF;
	}

	if(B[0] == '0')
	{
		dp0S[0] = INF, dp1S[0] = 2;
	}
	else
	{
		dp1S[0] = INF, dp0S[0] = 2;
	}

	for(int i = 1; i < n; ++i)
	{
		int co = min({dp[i-1],dpS[i-1],dp0[i-1],dp1[i-1],dp0S[i-1],dp1S[i-1]});
		if(A[i] == B[i]) dp[i] = co;
		else dp[i] = co+1;

		if(A[i] != B[i])
		{
			dpS[i] = min({dpS[i-1],dp0S[i-1],dp1S[i-1],co+1});
		}
		else if(B[i] == '0') dpS[i] = min({co+2,dp1S[i-1]});
		else dpS[i] = min({co+2,dp0S[i-1]});

		if(B[i] == '0')
		{
			dp0[i] = min({dp0[i-1],dp0S[i-1],co+1});
		}
		else dp0[i] = INF;

		if(B[i] == '1')
		{
			dp1[i] = min({dp1[i-1],dp1S[i-1],co+1});
		}
		else dp1[i] = INF;

		if(B[i] == '1')
		{
			dp0S[i] = min({dp0S[i-1],co+2,dpS[i-1]+1,dp0[i-1]+1});
		}
		else dp0S[i] = INF;

		if(B[i] == '0')
		{
			dp1S[i] = min({dp1S[i-1],co+2,dpS[i-1]+1,dp1[i-1]+1});
		}
		else dp1S[i] = INF;
	}

	int res = min({dp[n-1],dpS[n-1],dp0[n-1],dp1[n-1],dp0S[n-1],dp1S[n-1]});
	cout << res << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49