Submission #410275

#	Time	Username	Problem	Language	Result	Execution time	Memory
410275		alireza_kaviani	Lamps (JOI19_lamps)	C++11	100 / 100	84 ms	16036 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , dp[MAXN][3];
string s , t;

int valid(int i , int j){
	if(i < 0)	return 1;
	if(j == 0)	return (s[i] == t[i]);
	if(j == 1)	return (t[i] == '0');
	if(j == 2)	return (t[i] == '1');
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> s >> t;
	s = "." + s; t = "." + t;
	dp[0][1] = dp[0][2] = MOD;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 0 ; j < 3 ; j++){
			dp[i][j] = MOD;
			for(int k = 0 ; k < 3 ; k++){
				dp[i][j] = min(dp[i][j] , dp[i - 1][k] + ((j != k) + (j != k && j > 0 && k > 0)) + (valid(i , j) != valid(i - 1 , k)));
				//cout << dp[i - 1][k] + (j != k) + (valid(i , j) != valid(i - 1 , k)) << sep;
			}
			//cout << dp[i][j] << endl;
		}
		//cout << "==========" << endl;
	}
	int ans = MOD;
	for(int i = 0 ; i < 3 ; i++){
		ans = min(ans , dp[n][i] + (i != 0) + 1 - valid(n , i));
	}
	cout << ans / 2 << endl;

    return 0;
}
/*

*/

Compilation message (stderr)

lamp.cpp: In function 'int valid(int, int)':
lamp.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^

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