Submission #132629

#	Time	Username	Problem	Language	Result	Execution time	Memory
132629		hamzqq9	Lamps (JOI19_lamps)	C++14	100 / 100	144 ms	27836 KiB

lamp

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 20000000
#define N 1000005
#define MOD 998244353
#define KOK 700		
using namespace std;

int n;
int dp[N][3][2];
char s[2][N];

int main() {

	scanf("%d",&n);

	for(int i=0;i<2;i++) scanf("%s",s[i]+1);

	// 0 no 1 zero 2 black
	// 0 no 1 toggle

	for(int i=0;i<3;i++) for(int j=0;j<2;j++) dp[0][i][j]=inf;

	dp[0][0][0]=0;

	for(int i=0;i<n;i++) {

		for(int cg=0;cg<3;cg++) {

			for(int tg=0;tg<2;tg++) {

				dp[i+1][cg][tg]=inf;

				for(int c=0;c<3;c++) {

					for(int t=0;t<2;t++) {

						int cost=(c!=cg && cg)+(t!=tg && tg);
						int bit=(cg==1?0:cg==2?1:s[0][i+1]-'0')^tg;

						if(bit==(s[1][i+1]-'0')) umin(dp[i+1][cg][tg],dp[i][c][t]+cost);

					}

				}

			}

		}

	}

	int ans=inf;

	for(int c=0;c<3;c++) {

		for(int t=0;t<2;t++) {

			int bit=(c==1?0:c==2?1:s[0][n]-'0')^t;

			if(bit==(s[1][n]-'0')) umin(ans,dp[n][c][t]);

		}

	}

	printf("%d",ans);
 
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
lamp.cpp:27:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<2;i++) scanf("%s",s[i]+1);
                       ~~~~~^~~~~~~~~~~~~

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