Submission #154486

#	Time	Username	Problem	Language	Result	Execution time	Memory
154486		username	Lamps (JOI19_lamps)	C++14	100 / 100	207 ms	28132 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define MIN(x,y) (x=min(x,(y)))

const int maxn=1e6+9,inf=1e9;
int n,dp[maxn][2][3];
string a,b;

main(){
	cin>>n>>a>>b;
	a+='0',b+='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]-'0'^j^b[i]-'0'^k^l^m^1)MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
		}
		if(a[i]-'0'^b[i]-'0'^k^1)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:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
lamp.cpp: In function 'int main()':
lamp.cpp:18:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    if(b[i-1]-'0'^j^b[i]-'0'^k^l^m^1)MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
lamp.cpp:18:24: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    if(b[i-1]-'0'^j^b[i]-'0'^k^l^m^1)MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
lamp.cpp:20:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if(a[i]-'0'^b[i]-'0'^k^1)REP(l,0,3)MIN(dp[i+1][k][2],dp[i][j][l]+(!j&&k));

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