Submission #113519

#TimeUsernameProblemLanguageResultExecution timeMemory
113519raghav0307Lamps (JOI19_lamps)C++14
4 / 100
198 ms112840 KiB
/*raghav0307 - Raghav Gupta*/

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

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
#define int ll
const int MAX_SIZE = 1e6 + 5;
const int inf = 1e15;

int n;
string p, q;

int memo[MAX_SIZE][4];

int dp(int x, int y){
	if(x == -1){
		if(y == 0)	return 0;
		return 1;
	}
	if(memo[x][y] != -1)	return memo[x][y];
	int last_min = min(min(dp(x-1, 0), dp(x-1, 1) ), min(dp(x-1, 2), dp(x-1, 3)));
	if(y == 0){
		if(p[x] != q[x]) return memo[x][y] = inf;
		return memo[x][y] = last_min;
	}
	if(y == 1){
		if(q[x] != '0')	return memo[x][y] = min(dp(x-1, y) + ( (x == 0 or q[x-1] == '0') ? 1 : 0), last_min + 2);
		return memo[x][y]= min(dp(x-1, y), last_min + 1);
	} 
	if(y == 2){
		if(q[x] != '1')	return memo[x][y] = min(dp(x-1, y) + ( (x == 0 or q[x-1] == '1') ? 1 : 0), last_min + 2);
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
	if(y == 3){
		if(q[x] == p[x])	return memo[x][y] = min(dp(x-1, y) + ( x == 0 or q[x-1] != p[x-1] ? 1 : 0), last_min + 2);
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
}

signed main(){
	fast_io();
	cin >> n >> p >> q;
	memset(memo, -1, sizeof(memo));
	int ans = min(min(dp(n-1, 0), dp(n-1, 1)), min(dp(n-1,2), dp(n-1,3)));
	cout << ans << "\n";
	// for(int i = 0; i < n; i++){
	// 	for(int j = 0; j < 4; j++){
	// 		cout << memo[i][j] << " ";
	// 	}cout << "\n";
	// }
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'll dp(ll, ll)':
lamp.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...