Submission #154483

#	Time	Username	Problem	Language	Result	Execution time	Memory
154483		username	Lamps (JOI19_lamps)	C++14	100 / 100	92 ms	33700 KiB

lamp

#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){
					REP(l,0,2)REP(m,0,2){
						if((b[i-1]^j^b[i]^k^l^m)==0){
							MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
						}
					}
				}
				if(a[i]==(b[i]^k))REP(l,0,3)MIN(dp[i+1][k][2],dp[i][j][l]+(!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(){
      ^

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