Submission #166219

#TimeUsernameProblemLanguageResultExecution timeMemory
166219maruiiLamps (JOI19_lamps)C++14
100 / 100
204 ms27948 KiB
#include <bits/stdc++.h>
using namespace std;

char A[1000005], B[1000005];
int X[1000005][6];
int f(int x, int y) {
	return (x / 3 && y / 3 == 0) + (x % 3 != y % 3 && x % 3);
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	cin >> A + 1 >> B + 1;
	for (int i = 0; i <= N; ++i) fill(X[i], X[i] + 6, 1e9);
	X[0][0] = 0;
	for (int i = 1; i <= N; ++i) {
		int t = (A[i] - '0') << 1 | (B[i] - '0');
		if (t == 0) {
			for (int j = 0; j < 6; ++j) {
				X[i][0] = min(X[i][0], X[i - 1][j] + f(0, j));
				X[i][1] = min(X[i][1], X[i - 1][j] + f(1, j));
				X[i][5] = min(X[i][5], X[i - 1][j] + f(5, j));
			}
		}
		else if (t == 1) {
			for (int j = 0; j < 6; ++j) {
				X[i][3] = min(X[i][3], X[i - 1][j] + f(3, j));
				X[i][4] = min(X[i][4], X[i - 1][j] + f(4, j));
				X[i][2] = min(X[i][2], X[i - 1][j] + f(2, j));
			}
		}
		else if (t == 2) {
			for (int j = 0; j < 6; ++j) {
				X[i][3] = min(X[i][3], X[i - 1][j] + f(3, j));
				X[i][1] = min(X[i][1], X[i - 1][j] + f(1, j));
				X[i][5] = min(X[i][5], X[i - 1][j] + f(5, j));
			}
		}
		else {
			for (int j = 0; j < 6; ++j) {
				X[i][0] = min(X[i][0], X[i - 1][j] + f(0, j));
				X[i][4] = min(X[i][4], X[i - 1][j] + f(4, j));
				X[i][2] = min(X[i][2], X[i - 1][j] + f(2, j));
			}
		}
	}
	cout << *min_element(X[N], X[N] + 6);
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:13:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  cin >> A + 1 >> B + 1;
         ~~^~~
lamp.cpp:13:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  cin >> A + 1 >> B + 1;
                  ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...