Submission #143625

#	Time	Username	Problem	Language	Result	Execution time	Memory
143625		godwind	Lamps (JOI19_lamps)	C++14	100 / 100	104 ms	43540 KiB

lamp

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                        
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                        
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}
 
#define ghost signed
#define left left228
#define right right228
#define complex complex228
#define count count228
#define sin sin228
#define list list228

const int N = 1000 * 1000 + 228;
const int INF = 1e9 + 228;

int n;
int s[N], t[N];
int dp[N][3][2];
int color[N][3];
/*
0 - none
1 - color 0
2 - color 1
*/

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> n;
	char chaaa;
	for (int i = 1; i <= n; ++i) {
		cin >> chaaa;
		s[i] = (chaaa - '0');
	}
	for (int i = 1; i <= n; ++i) {
		cin >> chaaa;
		t[i] = (chaaa - '0');
	}
	for (int i = 1; i <= n; ++i) {
		color[i][0] = s[i];
		color[i][1] = 0;
		color[i][2] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		for (int c1 = 0; c1 < 3; ++c1) {
			for (int c2 = 0; c2 < 2; ++c2) {
				dp[i][c1][c2] = INF;
			}
		}
	}
	for (int c1 = 0; c1 < 3; ++c1) {
		for (int c2 = 0; c2 < 2; ++c2) {
			if ((color[1][c1] ^ c2) == t[1]) {
				dp[1][c1][c2] = (c1 > 0) + (c2 > 0);
			}
		}
	}
	for (int i = 1; i < n; ++i) {
		for (int c1 = 0; c1 < 3; ++c1) {
			for (int c2 = 0; c2 < 2; ++c2) {
				if (dp[i][c1][c2] == INF) continue;
				for (int b1 = 0; b1 < 3; ++b1) {
					for (int b2 = 0; b2 < 2; ++b2) {
						if ((color[i + 1][b1] ^ b2) != t[i + 1]) continue;
						uin(dp[i + 1][b1][b2], dp[i][c1][c2] + (b1 && b1 != c1) + (b2 && b2 != c2));
					}
				}
			}
		}
	}
	int res = INF;
	for (int c1 = 0; c1 < 3; ++c1) {
		for (int c2 = 0; c2 < 2; ++c2) uin(res, dp[n][c1][c2]);
	}
	cout << res << '\n';
    return 0;
} // kek ;
// Ого! Кажетсья это $#@!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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