Submission #260391

#	Time	Username	Problem	Language	Result	Execution time	Memory
260391		patrikpavic2	Lamps (JOI19_lamps)	C++17	100 / 100	591 ms	229372 KiB

lamp

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 500;

int A[N], B[N], dp[N][2][8], n;

int f(int x, int inv, int msk){
	if(x == n) return 0;
	if(dp[x][inv][msk] != -1) return dp[x][inv][msk];
	int ret = N;
	if(msk & 1) 
		ret = min(ret, f(x, inv, msk - 1));
	if(msk & 2) 
		ret = min(ret, f(x, inv, msk - 2));
	if(msk & 4)
		 ret = min(ret, f(x, inv, msk - 4));
	if(msk == 4)
		ret = min(ret, f(x, inv, 1));
	int zlm = B[x] ^ inv, jos = 0, ol = msk;
	if(A[x] == 0 && zlm == 0){
		if(msk & 4) msk -= 4;
		if((msk & 3) == 1)
			msk = 0;
	}
	if(A[x] == 1 && zlm == 1){
		if((msk & 6) == 2)
			msk -= 2;
	}
	if(A[x] == 1 && zlm == 0){
		if(msk & 4) msk -= 4;
		if(!(msk & 2))
			msk += 2, jos++;
		
	}
	if(A[x] == 0 && zlm == 1){
		if(msk == 3)
			msk = 1;
		if(msk == 2)
			msk += 4, jos++;
		if(msk == 0)
			msk = 1, jos++;
	}
	ret = min(ret, jos + min(f(x + 1, inv, msk), f(x + 1, !inv, msk) + (!inv)));
	return dp[x][inv][ol] = ret;
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		A[i] = c - '0';
	}
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		B[i] = c - '0';
	}
	printf("%d\n", min(f(0, 0, 0), 1 + f(0, 1, 0)));
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
lamp.cpp:55:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~
lamp.cpp:59:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~

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