Submission #154480

#TimeUsernameProblemLanguageResultExecution timeMemory
154480usernameLamps (JOI19_lamps)C++14
100 / 100
93 ms33788 KiB
#pragma GCC optimize("O3")
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
/*****************************************************************************/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
//																#define __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
const int maxn=1e6+9,inf=1e9;
int n,a[maxn],b[maxn],dp[maxn][2][3];

main(){
	IOS;
	cin>>n;
	REP(i,0,n){
		char c;cin>>c;
		a[i]=c-'0';
	}
	REP(i,0,n){
		char c;cin>>c;
		b[i]=c-'0';
	}
	a[n]=b[n]=0,++n;
	REP(i,0,n+1)REP(j,0,2)REP(k,0,3)dp[i][j][k]=inf;
	dp[0][0][2]=0;
	REP(i,0,n){
		REP(j,0,2){
			REP(k,0,2){
				MIN(dp[i+1][k][0],dp[i][j][2]+(!j&&k)+1);
				if(i){
					if((b[i-1]^j)==(b[i]^k)){
						MIN(dp[i+1][k][0],dp[i][j][0]+(!j&&k));
						MIN(dp[i+1][k][1],dp[i][j][1]+(!j&&k));
					}else{
						MIN(dp[i+1][k][1],dp[i][j][0]+(!j&&k)+1);
						MIN(dp[i+1][k][0],dp[i][j][1]+(!j&&k));
					}
				}
				if(a[i]==(b[i]^k)){
					MIN(dp[i+1][k][2],dp[i][j][0]+(!j&&k));
					MIN(dp[i+1][k][2],dp[i][j][1]+(!j&&k));
					MIN(dp[i+1][k][2],dp[i][j][2]+(!j&&k));
				}
			}
		}
	}
	cout<<dp[n][0][2]<<endl;
}

Compilation message (stderr)

lamp.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...