oj.uz

Submission #105075

# Submission time Handle Problem Language Result Execution time Memory
105075 2019-04-10T13:44:05 Z Just_Solve_The_Problem Lamps (JOI19_lamps) C++11
0 / 100
 26 ms 23928 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e6 + 7;

string a, b;
int n;
int dp[N][3][2];
/*
dp[pos][operation][xor]
operation
0 = off
1 = on
2 = do not touch
*/

main() {
	memset(dp, 63, sizeof dp);
	scanf("%d", &n);
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	dp[0][2][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			if (b[i] - '0' == j) {
				dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);
				dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1]);
				for (int l = 0; l < 3; l++) {
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][0] + 1);
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][1] + 1);
				}
			}
			if (b[i] - '0' == (j ^ 1)) {
				dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1]);
				dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][0] + 1);
				for (int l = 0; l < 3; l++) {
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][l][1] + 1);
				}
			}
			if (j == 2 && b[i] == a[i]) {
				for (int l = 0; l < 3; l++) {
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][0] + 1);
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][1] + 1);
				}
			}
			if (j == 2 && b[i] != a[i]) {
				for (int l = 0; l < 3; l++) {
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][l][0] + 1);
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][l][1]);
				}
			}
		}
	}
	int ans = dp[0][1][0];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 2; j++) {
			ans = min(ans, dp[n][i][j]);
		}
	}
	printf("%d\n", ans);
}

Compilation message

lamp.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
lamp.cpp: In function 'int main()':
lamp.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Incorrect 22 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Incorrect 22 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Incorrect 22 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -