Submission #755097

#	Time	Username	Problem	Language	Result	Execution time	Memory
755097		Dan4Life	Lamps (JOI19_lamps)	C++17	0 / 100	11 ms	7832 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define all(a) begin(a),end(a)

const int mxN = (int)2e5+10;

string s, ss;
int n, a[mxN], b[mxN], dp[mxN];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> s >> ss;
	for(int i = 0; i < n; i++) 
		a[i+1] = s[i]=='1', b[i+1] = ss[i]=='1';
	for(int i = 1; i <= n; i++){
		bool z=1, o=1, x=1, y = 1; dp[i]=i;
		for(int j = i; j>=1; j--){
			z&=!b[j], o&=b[j], x&=a[j]^b[j], y&=a[j]^!b[j];
			if(z or o or x) dp[i] = min(dp[i], dp[j-1]+1);
			if(y) dp[i] = min(dp[i], dp[j-1]);
		}
	}
	int ans = dp[n];
	for(int i = 1; i <= n; i++) a[i]^=1;
	for(int i = 1; i <= n; i++){
		bool z=1, o=1, x=1, y = 1; dp[i]=i;
		for(int j = i; j>=1; j--){
			z&=!b[j], o&=b[j], x&=a[j]^b[j], y&=a[j]^!b[j];
			if(z or o or x) dp[i] = min(dp[i], dp[j-1]+1);
			if(y) dp[i] = min(dp[i], dp[j-1]);
		}
	}
	cout << min(dp[n]+1,ans);
}

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