Submission #553765

#	Time	Username	Problem	Language	Result	Execution time	Memory
553765		MilosMilutinovic	Lamps (JOI19_lamps)	C++14	100 / 100	59 ms	27752 KiB

lamp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int INF = (int)1e9;
const int N = 1000050;
char a[N];
char b[N];
int n;
int dp[N][3][2];

int main()
{
	startTime = clock();

	scanf("%d", &n);
	scanf("%s", a + 1);
	scanf("%s", b + 1);
	for (int x = 0; x <= n; x++)
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 2; j++)
				dp[x][i][j] = INF;
	dp[0][0][0] = 0;
	for (int i = 1; i <= n; i++)
		for (int x = 0; x < 3; x++)
			for (int y = 0; y < 2; y++) {
				int v = (int)(a[i] - '0');
				if (x == 1)
					v = 0;
				if (x == 2)
					v = 1;
				if (y == 1)
					v ^= 1;
				if (v != (int)(b[i] - '0'))
					continue;
				for (int px = 0; px < 3; px++)
					for (int py = 0; py < 2; py++)
						dp[i][x][y] = min(dp[i][x][y], dp[i - 1][px][py] + (x != 0 && x != px ? 1 : 0) + (y != 0 && y != py ? 1 : 0));
			}
	int ans = INF;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 2; j++)
			ans = min(ans, dp[n][i][j]);
	printf("%d", ans);

	return 0;
}

Compilation message (stderr)

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

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