Submission #591795

#	Time	Username	Problem	Language	Result	Execution time	Memory
591795		UncoolAnon	Lamps (JOI19_lamps)	C++14	100 / 100	80 ms	59200 KiB

lamp

#include <bits/stdc++.h>


using namespace std; 

signed main(){
	ios_base::sync_with_stdio(0); 
	cin.tie(nullptr); 
	int n; 
	cin>>n; 
	string a,b; 
	cin>>a>>b; 
	vector<vector<int>> dp(n,vector<int>(6,2*n)); 
	if(a[0]==b[0])dp[0][0]=0; 
	if(a[0]!=b[0])dp[0][1]=1; 
	if(b[0]=='0')dp[0][2]=1,dp[0][5]=2; 
	if(b[0]=='1')dp[0][3]=2,dp[0][4]=1;
	for(int i=1;i<n;i++){
		if(a[i]==b[i]) dp[i][0]=*min_element(dp[i-1].begin(),dp[i-1].end()); 
		if(a[i]!=b[i]) dp[i][1]=min({dp[i-1][0]+1,dp[i-1][1],dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]}); 
		if(b[i]=='1'){
			dp[i][3]=min({dp[i-1][3],dp[i-1][2]+1,dp[i-1][0]+2,dp[i-1][1]+1,dp[i-1][4]+2,dp[i-1][5]+1}); 
			dp[i][4]=min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]}); 
		}
		else{
			dp[i][2]=min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2],dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+1}); 
			dp[i][5]=min({dp[i-1][0]+2,dp[i-1][1]+1,dp[i-1][2]+2,dp[i-1][3]+1,dp[i-1][4]+1,dp[i-1][5]}); 
		}
	}
	cout<<*min_element(dp[n-1].begin(),dp[n-1].end());
	return 0;  
}

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