Submission #107706

#	Time	Username	Problem	Language	Result	Execution time	Memory
107706		shayan_p	Lamps (JOI19_lamps)	C++14	100 / 100	61 ms	27992 KiB

lamp

// Faster!

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e6+10,mod=1e9+7;
const ll inf=1e18;

int dp[maxn][3][2];
string A,B;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n>>A>>B;
    for(int i=1;i<=n;i++){
	int a=A[i-1]-'0',b=B[i-1]-'0';
	for(int j=0;j<3;j++)
	    for(int k=0;k<2;k++)
		dp[i][j][k]=n;
	if(a==b){
	    for(int j=0;j<3;j++)
		for(int k=0;k<2;k++)
		    dp[i][j][k]=min(dp[i][j][k],dp[i-1][0][0]);
	}
	else{
	    for(int j=0;j<3;j++)
		for(int k=0;k<2;k++)
		    dp[i][j][k]=min(dp[i][j][k],(k==1 ? 0 : 1) + dp[i-1][0][1]);
	}
	for(int j=0;j<3;j++)
	    for(int k=0;k<2;k++)
		dp[i][j][k]=min(dp[i][j][k],(j==b+1 ? 0 : 1) + dp[i-1][b+1][0] );
	for(int j=0;j<3;j++)
	    for(int k=0;k<2;k++)
		dp[i][j][k]=min(dp[i][j][k],(j==1-b+1 ? 0 : 1) + (k==1 ? 0 : 1) + dp[i-1][1-b+1][1] );
    }
    return cout<<dp[n][0][0]<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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