# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

153052 | 2019-09-11T19:16:42 Z | fedoseevtimofey | Lamps (JOI19_lamps) | C++14 | 358 ms | 41608 KB |

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int N = 1e6 + 7; int dp[N][2][2][2]; int a[N], b[N]; const int Inf = 1e9 + 7; bool valid(int i, int j, int k, int id) { if (i == 1 && j == 1) return false; int x = a[id]; if (i) x = 0; if (j) x = 1; if (k) x ^= 1; return x == b[id]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n; cin >> n; for (int i = 0; i < n; ++i) { char c; cin >> c; a[i] = c - '0'; } for (int i = 0; i < n; ++i) { char c; cin >> c; b[i] = c - '0'; } for (int i = 0; i < N; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { for (int t = 0; t < 2; ++t) { dp[i][j][k][t] = Inf; } } } } dp[0][0][0][0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { for (int t = 0; t < 2; ++t) { for (int nj = 0; nj < 2; ++nj) { for (int nk = 0; nk < 2; ++nk) { for (int nt = 0; nt < 2; ++nt) { if (valid(nj, nk, nt, i)) { int delta = (nj > j) + (nk > k) + (nt > t); dp[i + 1][nj][nk][nt] = min(dp[i + 1][nj][nk][nt], dp[i][j][k][t] + delta); } } } } } } } } int ans = Inf; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) ans = min(ans, dp[n][i][j][k]); cout << ans << '\n'; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 29 ms | 31864 KB | Output is correct |

2 | Correct | 29 ms | 31736 KB | Output is correct |

3 | Correct | 30 ms | 31736 KB | Output is correct |

4 | Correct | 29 ms | 31608 KB | Output is correct |

5 | Correct | 29 ms | 31608 KB | Output is correct |

6 | Correct | 29 ms | 31608 KB | Output is correct |

7 | Correct | 29 ms | 31608 KB | Output is correct |

8 | Correct | 28 ms | 31608 KB | Output is correct |

9 | Correct | 29 ms | 31612 KB | Output is correct |

10 | Correct | 29 ms | 31628 KB | Output is correct |

11 | Correct | 29 ms | 31608 KB | Output is correct |

12 | Correct | 29 ms | 31608 KB | Output is correct |

13 | Correct | 35 ms | 31604 KB | Output is correct |

14 | Correct | 29 ms | 31608 KB | Output is correct |

15 | Correct | 29 ms | 31608 KB | Output is correct |

16 | Correct | 29 ms | 31608 KB | Output is correct |

17 | Correct | 29 ms | 31608 KB | Output is correct |

18 | Correct | 29 ms | 31608 KB | Output is correct |

19 | Correct | 29 ms | 31608 KB | Output is correct |

20 | Correct | 29 ms | 31608 KB | Output is correct |

21 | Correct | 29 ms | 31608 KB | Output is correct |

22 | Correct | 29 ms | 31608 KB | Output is correct |

23 | Correct | 29 ms | 31608 KB | Output is correct |

24 | Correct | 29 ms | 31608 KB | Output is correct |

25 | Correct | 29 ms | 31608 KB | Output is correct |

26 | Correct | 29 ms | 31608 KB | Output is correct |

27 | Correct | 29 ms | 31608 KB | Output is correct |

28 | Correct | 34 ms | 31612 KB | Output is correct |

29 | Correct | 33 ms | 31608 KB | Output is correct |

30 | Correct | 29 ms | 31608 KB | Output is correct |

31 | Correct | 30 ms | 31736 KB | Output is correct |

32 | Correct | 31 ms | 31736 KB | Output is correct |

33 | Correct | 30 ms | 31608 KB | Output is correct |

34 | Correct | 29 ms | 31608 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 29 ms | 31864 KB | Output is correct |

2 | Correct | 29 ms | 31736 KB | Output is correct |

3 | Correct | 30 ms | 31736 KB | Output is correct |

4 | Correct | 29 ms | 31608 KB | Output is correct |

5 | Correct | 29 ms | 31608 KB | Output is correct |

6 | Correct | 29 ms | 31608 KB | Output is correct |

7 | Correct | 29 ms | 31608 KB | Output is correct |

8 | Correct | 28 ms | 31608 KB | Output is correct |

9 | Correct | 29 ms | 31612 KB | Output is correct |

10 | Correct | 29 ms | 31628 KB | Output is correct |

11 | Correct | 29 ms | 31608 KB | Output is correct |

12 | Correct | 29 ms | 31608 KB | Output is correct |

13 | Correct | 35 ms | 31604 KB | Output is correct |

14 | Correct | 29 ms | 31608 KB | Output is correct |

15 | Correct | 29 ms | 31608 KB | Output is correct |

16 | Correct | 29 ms | 31608 KB | Output is correct |

17 | Correct | 29 ms | 31608 KB | Output is correct |

18 | Correct | 29 ms | 31608 KB | Output is correct |

19 | Correct | 29 ms | 31608 KB | Output is correct |

20 | Correct | 29 ms | 31608 KB | Output is correct |

21 | Correct | 29 ms | 31608 KB | Output is correct |

22 | Correct | 29 ms | 31608 KB | Output is correct |

23 | Correct | 29 ms | 31608 KB | Output is correct |

24 | Correct | 29 ms | 31608 KB | Output is correct |

25 | Correct | 29 ms | 31608 KB | Output is correct |

26 | Correct | 29 ms | 31608 KB | Output is correct |

27 | Correct | 29 ms | 31608 KB | Output is correct |

28 | Correct | 34 ms | 31612 KB | Output is correct |

29 | Correct | 33 ms | 31608 KB | Output is correct |

30 | Correct | 29 ms | 31608 KB | Output is correct |

31 | Correct | 30 ms | 31736 KB | Output is correct |

32 | Correct | 31 ms | 31736 KB | Output is correct |

33 | Correct | 30 ms | 31608 KB | Output is correct |

34 | Correct | 29 ms | 31608 KB | Output is correct |

35 | Correct | 30 ms | 31736 KB | Output is correct |

36 | Correct | 30 ms | 31736 KB | Output is correct |

37 | Correct | 30 ms | 31644 KB | Output is correct |

38 | Correct | 30 ms | 31636 KB | Output is correct |

39 | Correct | 30 ms | 31608 KB | Output is correct |

40 | Correct | 29 ms | 31708 KB | Output is correct |

41 | Correct | 30 ms | 31736 KB | Output is correct |

42 | Correct | 29 ms | 31608 KB | Output is correct |

43 | Correct | 30 ms | 31736 KB | Output is correct |

44 | Correct | 30 ms | 31696 KB | Output is correct |

45 | Correct | 29 ms | 31608 KB | Output is correct |

46 | Correct | 30 ms | 31604 KB | Output is correct |

47 | Correct | 30 ms | 31736 KB | Output is correct |

48 | Correct | 29 ms | 31608 KB | Output is correct |

49 | Correct | 41 ms | 31736 KB | Output is correct |

50 | Correct | 30 ms | 31608 KB | Output is correct |

51 | Correct | 30 ms | 31608 KB | Output is correct |

52 | Correct | 30 ms | 31608 KB | Output is correct |

53 | Correct | 30 ms | 31608 KB | Output is correct |

54 | Correct | 30 ms | 31716 KB | Output is correct |

55 | Correct | 30 ms | 31736 KB | Output is correct |

56 | Correct | 30 ms | 31676 KB | Output is correct |

57 | Correct | 30 ms | 31736 KB | Output is correct |

58 | Correct | 30 ms | 31608 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 29 ms | 31624 KB | Output is correct |

2 | Correct | 29 ms | 31708 KB | Output is correct |

3 | Correct | 30 ms | 31608 KB | Output is correct |

4 | Correct | 29 ms | 31736 KB | Output is correct |

5 | Correct | 29 ms | 31736 KB | Output is correct |

6 | Correct | 29 ms | 31608 KB | Output is correct |

7 | Correct | 332 ms | 41528 KB | Output is correct |

8 | Correct | 345 ms | 41480 KB | Output is correct |

9 | Correct | 344 ms | 41544 KB | Output is correct |

10 | Correct | 343 ms | 41468 KB | Output is correct |

11 | Correct | 341 ms | 41468 KB | Output is correct |

12 | Correct | 336 ms | 41592 KB | Output is correct |

13 | Correct | 332 ms | 41464 KB | Output is correct |

14 | Correct | 341 ms | 41592 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 29 ms | 31864 KB | Output is correct |

2 | Correct | 29 ms | 31736 KB | Output is correct |

3 | Correct | 30 ms | 31736 KB | Output is correct |

4 | Correct | 29 ms | 31608 KB | Output is correct |

5 | Correct | 29 ms | 31608 KB | Output is correct |

6 | Correct | 29 ms | 31608 KB | Output is correct |

7 | Correct | 29 ms | 31608 KB | Output is correct |

8 | Correct | 28 ms | 31608 KB | Output is correct |

9 | Correct | 29 ms | 31612 KB | Output is correct |

10 | Correct | 29 ms | 31628 KB | Output is correct |

11 | Correct | 29 ms | 31608 KB | Output is correct |

12 | Correct | 29 ms | 31608 KB | Output is correct |

13 | Correct | 35 ms | 31604 KB | Output is correct |

14 | Correct | 29 ms | 31608 KB | Output is correct |

15 | Correct | 29 ms | 31608 KB | Output is correct |

16 | Correct | 29 ms | 31608 KB | Output is correct |

17 | Correct | 29 ms | 31608 KB | Output is correct |

18 | Correct | 29 ms | 31608 KB | Output is correct |

19 | Correct | 29 ms | 31608 KB | Output is correct |

20 | Correct | 29 ms | 31608 KB | Output is correct |

21 | Correct | 29 ms | 31608 KB | Output is correct |

22 | Correct | 29 ms | 31608 KB | Output is correct |

23 | Correct | 29 ms | 31608 KB | Output is correct |

24 | Correct | 29 ms | 31608 KB | Output is correct |

25 | Correct | 29 ms | 31608 KB | Output is correct |

26 | Correct | 29 ms | 31608 KB | Output is correct |

27 | Correct | 29 ms | 31608 KB | Output is correct |

28 | Correct | 34 ms | 31612 KB | Output is correct |

29 | Correct | 33 ms | 31608 KB | Output is correct |

30 | Correct | 29 ms | 31608 KB | Output is correct |

31 | Correct | 30 ms | 31736 KB | Output is correct |

32 | Correct | 31 ms | 31736 KB | Output is correct |

33 | Correct | 30 ms | 31608 KB | Output is correct |

34 | Correct | 29 ms | 31608 KB | Output is correct |

35 | Correct | 30 ms | 31736 KB | Output is correct |

36 | Correct | 30 ms | 31736 KB | Output is correct |

37 | Correct | 30 ms | 31644 KB | Output is correct |

38 | Correct | 30 ms | 31636 KB | Output is correct |

39 | Correct | 30 ms | 31608 KB | Output is correct |

40 | Correct | 29 ms | 31708 KB | Output is correct |

41 | Correct | 30 ms | 31736 KB | Output is correct |

42 | Correct | 29 ms | 31608 KB | Output is correct |

43 | Correct | 30 ms | 31736 KB | Output is correct |

44 | Correct | 30 ms | 31696 KB | Output is correct |

45 | Correct | 29 ms | 31608 KB | Output is correct |

46 | Correct | 30 ms | 31604 KB | Output is correct |

47 | Correct | 30 ms | 31736 KB | Output is correct |

48 | Correct | 29 ms | 31608 KB | Output is correct |

49 | Correct | 41 ms | 31736 KB | Output is correct |

50 | Correct | 30 ms | 31608 KB | Output is correct |

51 | Correct | 30 ms | 31608 KB | Output is correct |

52 | Correct | 30 ms | 31608 KB | Output is correct |

53 | Correct | 30 ms | 31608 KB | Output is correct |

54 | Correct | 30 ms | 31716 KB | Output is correct |

55 | Correct | 30 ms | 31736 KB | Output is correct |

56 | Correct | 30 ms | 31676 KB | Output is correct |

57 | Correct | 30 ms | 31736 KB | Output is correct |

58 | Correct | 30 ms | 31608 KB | Output is correct |

59 | Correct | 29 ms | 31624 KB | Output is correct |

60 | Correct | 29 ms | 31708 KB | Output is correct |

61 | Correct | 30 ms | 31608 KB | Output is correct |

62 | Correct | 29 ms | 31736 KB | Output is correct |

63 | Correct | 29 ms | 31736 KB | Output is correct |

64 | Correct | 29 ms | 31608 KB | Output is correct |

65 | Correct | 332 ms | 41528 KB | Output is correct |

66 | Correct | 345 ms | 41480 KB | Output is correct |

67 | Correct | 344 ms | 41544 KB | Output is correct |

68 | Correct | 343 ms | 41468 KB | Output is correct |

69 | Correct | 341 ms | 41468 KB | Output is correct |

70 | Correct | 336 ms | 41592 KB | Output is correct |

71 | Correct | 332 ms | 41464 KB | Output is correct |

72 | Correct | 341 ms | 41592 KB | Output is correct |

73 | Correct | 346 ms | 41476 KB | Output is correct |

74 | Correct | 334 ms | 41564 KB | Output is correct |

75 | Correct | 337 ms | 41464 KB | Output is correct |

76 | Correct | 335 ms | 41464 KB | Output is correct |

77 | Correct | 353 ms | 41480 KB | Output is correct |

78 | Correct | 344 ms | 41568 KB | Output is correct |

79 | Correct | 333 ms | 41468 KB | Output is correct |

80 | Correct | 332 ms | 41464 KB | Output is correct |

81 | Correct | 336 ms | 41464 KB | Output is correct |

82 | Correct | 340 ms | 41596 KB | Output is correct |

83 | Correct | 337 ms | 41592 KB | Output is correct |

84 | Correct | 338 ms | 41608 KB | Output is correct |

85 | Correct | 339 ms | 41464 KB | Output is correct |

86 | Correct | 348 ms | 41472 KB | Output is correct |

87 | Correct | 339 ms | 41464 KB | Output is correct |

88 | Correct | 343 ms | 41592 KB | Output is correct |

89 | Correct | 337 ms | 41468 KB | Output is correct |

90 | Correct | 342 ms | 41592 KB | Output is correct |

91 | Correct | 345 ms | 41592 KB | Output is correct |

92 | Correct | 358 ms | 41464 KB | Output is correct |

93 | Correct | 349 ms | 41464 KB | Output is correct |

94 | Correct | 355 ms | 41584 KB | Output is correct |

95 | Correct | 356 ms | 41472 KB | Output is correct |

96 | Correct | 353 ms | 41476 KB | Output is correct |

97 | Correct | 351 ms | 41592 KB | Output is correct |

98 | Correct | 347 ms | 41464 KB | Output is correct |

99 | Correct | 346 ms | 41436 KB | Output is correct |

100 | Correct | 347 ms | 41464 KB | Output is correct |

101 | Correct | 358 ms | 41464 KB | Output is correct |

102 | Correct | 350 ms | 41472 KB | Output is correct |