oj.uz

Submission #1097662

# Submission time Handle Problem Language Result Execution time Memory
1097662 2024-10-07T23:13:17 Z ten_xd Lamps (JOI19_lamps) C++17
4 / 100
 20 ms 29016 KB 
#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,dp0[i-1]+1});
		}
		else dp0S[i] = INF;

		if(B[i] == '0')
		{
			dp1S[i] = min({dp1S[i-1],co+2,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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Incorrect 1 ms 10588 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Incorrect 1 ms 10588 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10708 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 17 ms 29016 KB Output is correct
8 Correct 18 ms 28832 KB Output is correct
9 Correct 18 ms 28840 KB Output is correct
10 Correct 18 ms 28828 KB Output is correct
11 Correct 18 ms 28848 KB Output is correct
12 Correct 19 ms 28836 KB Output is correct
13 Correct 20 ms 28832 KB Output is correct
14 Correct 18 ms 28848 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Incorrect 1 ms 10588 KB Output isn't correct
14 Halted 0 ms 0 KB -