Submission #294749

#	Time	Username	Problem	Language	Result	Execution time	Memory
294749		arnold518	Lamps (JOI19_lamps)	C++14	100 / 100	267 ms	22016 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e6;

int N, A[MAXN+10], B[MAXN+10];
int dp[MAXN+10][3];

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%1d", &A[i]);
	for(int i=1; i<=N; i++) scanf("%1d", &B[i]);

	dp[1][0]=1+((0^B[1])==1);
	dp[1][1]=1+((1^B[1])==1);
	dp[1][2]=((A[1]^B[1])==1);
	for(int i=2; i<=N; i++)
	{
		dp[i][0]=dp[i][1]=dp[i][2]=987654321;

		dp[i][0]=min(dp[i][0], dp[i-1][0]+((0^B[i])==1 && (0^B[i-1])==0));
		dp[i][0]=min(dp[i][0], dp[i-1][1]+((0^B[i])==1 && (1^B[i-1])==0)+1);
		dp[i][0]=min(dp[i][0], dp[i-1][2]+((0^B[i])==1 && (A[i-1]^B[i-1])==0)+1);
		
		dp[i][1]=min(dp[i][1], dp[i-1][0]+((1^B[i])==1 && (0^B[i-1])==0)+1);
		dp[i][1]=min(dp[i][1], dp[i-1][1]+((1^B[i])==1 && (1^B[i-1])==0));
		dp[i][1]=min(dp[i][1], dp[i-1][2]+((1^B[i])==1 && (A[i-1]^B[i-1])==0)+1);

		dp[i][2]=min(dp[i][2], dp[i-1][0]+((A[i]^B[i])==1 && (0^B[i-1])==0));
		dp[i][2]=min(dp[i][2], dp[i-1][1]+((A[i]^B[i])==1 && (1^B[i-1])==0));
		dp[i][2]=min(dp[i][2], dp[i-1][2]+((A[i]^B[i])==1 && (A[i-1]^B[i-1])==0));
	}
	printf("%d\n", min({dp[N][0], dp[N][1], dp[N][2]}));
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
lamp.cpp:16:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  for(int i=1; i<=N; i++) scanf("%1d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~
lamp.cpp:17:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  for(int i=1; i<=N; i++) scanf("%1d", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~

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