Submission #210734

#	Time	Username	Problem	Language	Result	Execution time	Memory
210734		arman_ferdous	Lamps (JOI19_lamps)	C++17	100 / 100	252 ms	113912 KiB

lamp

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

using ll = long long;
const int N = 1e6+10;
const int oo = 1e9;

int n, ans;
char a[N], b[N];

int dp[8][N];

int get(int x, int mask) {
	if(mask & 1) x = 0;
	if(mask & 2) x = 1;
	if(mask & 4) x ^= 1;
	return x;
}

int DP(int prev, int pos) {
	if(pos < 0) return 0;
	if(dp[prev][pos] != -1) return dp[prev][pos];

	int &ret = dp[prev][pos]; ret = oo;
	for(int i = 0; i < 7; i++)
		if(get(a[pos] - '0', i) == b[pos] - '0')
			ret = min(ret, __builtin_popcount(~prev & i) + DP(i, pos - 1));
	return ret;
}

int main() {
	scanf("%d", &n);	
	scanf(" %s %s", a, b);
    memset(dp, -1, sizeof dp);
    printf("%d\n", DP(0, n - 1));
	return 0;
}

Compilation message (stderr)

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

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