Submission #624412

#	Time	Username	Problem	Language	Result	Execution time	Memory
624412		pooyashams	Lamps (JOI19_lamps)	C++14	100 / 100	46 ms	51224 KiB

lamp

#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 1e6+10;
const int inf = 1e9;

int dp[maxn][2][3];
int mnt[maxn][2];
int mna[maxn][3];
int mno[maxn];

char s[maxn];
char t[maxn];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	for(int i = 0; i < maxn; i++)
		for(int j = 0; j < 2; j++)
			for(int k = 0; k < 3; k++)
				dp[i][j][k] = inf;
	{
		int i = 0;
		dp[i][0][0] = 0;
		mnt[i][0] = min(dp[i][0][0], min(dp[i][0][1], dp[i][0][2]));
		mnt[i][1] = min(dp[i][1][0], min(dp[i][1][1], dp[i][1][2]));
		mno[i] = min(mnt[i][0], mnt[i][1]);
		for(int k = 0; k < 3; k++)
			mna[i][k] = min(dp[i][0][k], dp[i][1][k]);
	}
	int n; cin >> n;
	cin >> (s+1);
	cin >> (t+1);
	for(int i = 1; i <= n; i++)
	{
		if(s[i] == t[i])
		{
			dp[i][0][0] = mno[i-1];
			dp[i][1][0] = inf;
		}
		else
		{
			dp[i][0][0] = inf;
			dp[i][1][0] = min(mnt[i-1][1], mno[i-1]+1);
		}
		//
		if(t[i] == '1')
		{
			dp[i][0][1] = inf;
			dp[i][0][2] = min(mno[i-1]+1, mna[i-1][2]);
			dp[i][1][1] = min( min(mnt[i-1][1]+1, mna[i-1][1]+1), min(dp[i-1][1][1], 2+mno[i-1]) );
			dp[i][1][2] = inf;
		}
		else
		{
			dp[i][0][1] = min(mno[i-1]+1, mna[i-1][1]);
			dp[i][0][2] = inf;
			dp[i][1][1] = inf;
			dp[i][1][2] = min( min(mnt[i-1][1]+1, mna[i-1][2]+1), min(dp[i-1][1][2], 2+mno[i-1]) );
		}
		//
		mnt[i][0] = min(dp[i][0][0], min(dp[i][0][1], dp[i][0][2]));
		mnt[i][1] = min(dp[i][1][0], min(dp[i][1][1], dp[i][1][2]));
		mno[i] = min(mnt[i][0], mnt[i][1]);
		for(int k = 0; k < 3; k++)
			mna[i][k] = min(dp[i][0][k], dp[i][1][k]);
		//cerr << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][0][2] << endl;
		//cerr << dp[i][1][0] << " " << dp[i][1][1] << " " << dp[i][1][2] << endl;
		//cerr << "---- " << (s[i] == t[i]) << endl;
	}
	cout << mno[n] << endl;
	return 0;
}

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