Submission #708909

#	Time	Username	Problem	Language	Result	Execution time	Memory
708909		alvingogo	Lamps (JOI19_lamps)	C++14	100 / 100	33 ms	16200 KiB

lamp

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int main(){
    AquA;
	int n;
	cin >> n;
	string a,b;
	cin >> a >> b;
	vector<array<int,3> > dp(n);
	dp[0][0]=1+(0!=b[0]-'0');
	dp[0][1]=1+(1!=b[0]-'0');
	dp[0][2]=(a[0]!=b[0]);
	for(int i=1;i<n;i++){
		dp[i][0]=dp[i][1]=dp[i][2]=1e9;
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				int c=j;
				if(c==2){
					c=a[i-1]-'0';
				}
				int d=k;
				if(d==2){
					d=a[i]-'0';
				}
				int cnt=0,cz=0;
				if(k<=1 && k!=j){
					cnt=1;
				}
				if(d!=b[i]-'0' && c==b[i-1]-'0'){
					cz=1;
				}
				dp[i][k]=min(dp[i][k],dp[i-1][j]+cnt+cz);
			}
		}
	}
	cout << min({dp[n-1][0],dp[n-1][1],dp[n-1][2]}) << "\n";
    return 0;
}

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