Submission #113911

#	Time	Username	Problem	Language	Result	Execution time	Memory
113911		raghav0307	Lamps (JOI19_lamps)	C++14	4 / 100	203 ms	106320 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;
#define int ll
const int MAX_SIZE = 1e6 + 5;
const int inf = 1e15;

int n;
string p, q;

int memo[MAX_SIZE][3];

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), MAX_SIZE));
	if(y == 0){
		if(p[x] != q[x]) return memo[x][y] = min(dp(x-1, y) + ( (x == 0 or q[x-1] == p[x-1]) ? 1 : 0), last_min + 1);
		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), MAX_SIZE));
	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]
 }
 ^

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