Submission #113504

#	Time	Username	Problem	Language	Result	Execution time	Memory
113504		raghav0307	Lamps (JOI19_lamps)	C++14	4 / 100	142 ms	82764 KiB

lamp

/*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;
const int MAX_SIZE = 1e6 + 5;
const int inf = 1e7;

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] = inf;
		return memo[x][y]= min(dp(x-1, y), last_min + 1);
	} 
	if(y == 2){
		if(q[x] != '1')	return memo[x][y] = inf;
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
	if(y == 3){
		if(q[x] == p[x])	return memo[x][y] = inf;
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
}

int 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 'int dp(int, int)':
lamp.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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