Submission #114300

#	Time	Username	Problem	Language	Result	Execution time	Memory
114300		tincamatei	Lamps (JOI19_lamps)	C++14	100 / 100	144 ms	27896 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

char getChar(FILE *fin) {
	char ch = fgetc(fin);
	while(!isdigit(ch))
		ch = fgetc(fin);
	return ch;
}

const int MAX_N = 1000000;

char str1[1+MAX_N];
char str2[1+MAX_N];

int dp[1+MAX_N][3][2];

// dp[N][0/1/2][0/1] = numarul minim de operatii daca la sfarsit n-am/am set 0/am set 1 si daca n-am/am operatie de xor

int main() {
	int N, rez = MAX_N;
	scanf("%d", &N);

	for(int i = 1; i <= N; ++i)
		str1[i] = getChar(stdin);
	for(int i = 1; i <= N; ++i)
		str2[i] = getChar(stdin);

	for(int i = 0; i <= N; ++i)
		for(int setmask = 0; setmask < 3; ++setmask)
			for(int xormask = 0; xormask < 2; ++xormask)
				dp[i][setmask][xormask] = MAX_N + 1;
	dp[0][0][0] = 0;

	for(int i = 1; i <= N; ++i) {
		for(int setmask1 = 0; setmask1 < 3; ++setmask1)
			for(int xormask1 = 0; xormask1 < 2; ++xormask1)
				for(int setmask2 = 0; setmask2 < 3; ++setmask2)
					for(int xormask2 = 0; xormask2 < 2; ++xormask2) {
						char chVal = str1[i];
						int cost = 0;

						if(setmask2 == 1)
							chVal = '0';
						else if(setmask2 == 2)
							chVal = '1';

						if(xormask2 == 1)
							chVal = '0' + '1' - chVal;
						
						if(setmask1 != setmask2 && setmask2 != 0)
							++cost;
						if(xormask1 != xormask2 && xormask2 != 0)
							++cost;
						
						if(chVal == str2[i])
							dp[i][setmask2][xormask2] = min(dp[i - 1][setmask1][xormask1] + cost, 
							                                dp[i][setmask2][xormask2]);
					}
	}

	for(int setmask = 0; setmask < 3; ++setmask)
		for(int xormask = 0; xormask < 2; ++xormask)
			rez = min(rez, dp[N][setmask][xormask]);

	printf("%d", rez);
	return 0;
}

Compilation message (stderr)

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

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