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

218111 | 2020-04-01T08:38:05 Z | PeppaPig | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 152 ms | 131748 KB |

#include <bits/stdc++.h> #define long long long using namespace std; const int N = 205; int n, l, ans; int x[N], t[N]; long L[N][N][N], R[N][N][N]; long d(int a, int b) { return min(abs(x[b] - x[a]), l - abs(x[b] - x[a])); } int main() { scanf("%d %d", &n, &l); for(int i = 1; i <= n; i++) scanf("%d", x + i); for(int i = 1; i <= n; i++) scanf("%d", t + i); x[n + 1] = l; for(int k = 0; k <= n; k++) for(int i = 0; i <= n; i++) for(int j = n + 1; j; j--) { if(j <= i || (!i && j == n + 1 && !k)) continue; L[k][i][j] = R[k][i][j] = 1e18; if(i) L[k][i][j] = min({L[k][i][j], L[k][i-1][j] + d(i-1, i), R[k][i-1][j] + d(j, i)}); if(j <= n) R[k][i][j] = min({R[k][i][j], L[k][i][j+1] + d(i, j), R[k][i][j+1] + d(j+1, j)}); if(k) { long T; if(i) { T = min(L[k-1][i-1][j] + d(i-1, i), R[k-1][i-1][j] + d(j, i)); if(T <= t[i]) L[k][i][j] = min(L[k][i][j], T); } if(j <= n) { T = min(L[k-1][i][j+1] + d(i, j), R[k-1][i][j+1] + d(j+1, j)); if(T <= t[j]) R[k][i][j] = min(R[k][i][j], T); } } if(L[k][i][j] != 1e18 || R[k][i][j] != 1e18) ans = max(ans, k); } printf("%d\n", ans); return 0; }

### Compilation message

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

1 | Correct | 5 ms | 512 KB | Output is correct |

2 | Correct | 4 ms | 512 KB | Output is correct |

3 | Correct | 5 ms | 768 KB | Output is correct |

4 | Correct | 5 ms | 512 KB | Output is correct |

5 | Correct | 5 ms | 512 KB | Output is correct |

6 | Correct | 5 ms | 896 KB | Output is correct |

7 | Correct | 5 ms | 640 KB | Output is correct |

8 | Correct | 5 ms | 768 KB | Output is correct |

9 | Correct | 6 ms | 896 KB | Output is correct |

10 | Correct | 4 ms | 384 KB | Output is correct |

11 | Correct | 6 ms | 384 KB | Output is correct |

12 | Correct | 5 ms | 896 KB | Output is correct |

13 | Correct | 13 ms | 1024 KB | Output is correct |

14 | Correct | 5 ms | 512 KB | Output is correct |

15 | Correct | 5 ms | 640 KB | Output is correct |

16 | Correct | 5 ms | 1024 KB | Output is correct |

17 | Correct | 5 ms | 1024 KB | Output is correct |

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

1 | Correct | 5 ms | 512 KB | Output is correct |

2 | Correct | 4 ms | 512 KB | Output is correct |

3 | Correct | 5 ms | 768 KB | Output is correct |

4 | Correct | 5 ms | 512 KB | Output is correct |

5 | Correct | 5 ms | 512 KB | Output is correct |

6 | Correct | 5 ms | 896 KB | Output is correct |

7 | Correct | 5 ms | 640 KB | Output is correct |

8 | Correct | 5 ms | 768 KB | Output is correct |

9 | Correct | 6 ms | 896 KB | Output is correct |

10 | Correct | 4 ms | 384 KB | Output is correct |

11 | Correct | 6 ms | 384 KB | Output is correct |

12 | Correct | 5 ms | 896 KB | Output is correct |

13 | Correct | 13 ms | 1024 KB | Output is correct |

14 | Correct | 5 ms | 512 KB | Output is correct |

15 | Correct | 5 ms | 640 KB | Output is correct |

16 | Correct | 5 ms | 1024 KB | Output is correct |

17 | Correct | 5 ms | 1024 KB | Output is correct |

18 | Correct | 5 ms | 1152 KB | Output is correct |

19 | Correct | 5 ms | 768 KB | Output is correct |

20 | Correct | 5 ms | 1024 KB | Output is correct |

21 | Correct | 5 ms | 1152 KB | Output is correct |

22 | Correct | 5 ms | 768 KB | Output is correct |

23 | Correct | 5 ms | 1280 KB | Output is correct |

24 | Correct | 5 ms | 1024 KB | Output is correct |

25 | Correct | 5 ms | 1152 KB | Output is correct |

26 | Correct | 5 ms | 1152 KB | Output is correct |

27 | Correct | 5 ms | 640 KB | Output is correct |

28 | Correct | 5 ms | 768 KB | Output is correct |

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

30 | Correct | 5 ms | 1280 KB | Output is correct |

31 | Correct | 5 ms | 1152 KB | Output is correct |

32 | Correct | 5 ms | 1024 KB | Output is correct |

33 | Correct | 5 ms | 1280 KB | Output is correct |

34 | Correct | 5 ms | 1280 KB | Output is correct |

35 | Correct | 5 ms | 1280 KB | Output is correct |

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

1 | Correct | 5 ms | 512 KB | Output is correct |

2 | Correct | 4 ms | 512 KB | Output is correct |

3 | Correct | 5 ms | 768 KB | Output is correct |

4 | Correct | 5 ms | 512 KB | Output is correct |

5 | Correct | 5 ms | 512 KB | Output is correct |

6 | Correct | 5 ms | 896 KB | Output is correct |

7 | Correct | 5 ms | 640 KB | Output is correct |

8 | Correct | 5 ms | 768 KB | Output is correct |

9 | Correct | 6 ms | 896 KB | Output is correct |

10 | Correct | 4 ms | 384 KB | Output is correct |

11 | Correct | 6 ms | 384 KB | Output is correct |

12 | Correct | 5 ms | 896 KB | Output is correct |

13 | Correct | 13 ms | 1024 KB | Output is correct |

14 | Correct | 5 ms | 512 KB | Output is correct |

15 | Correct | 5 ms | 640 KB | Output is correct |

16 | Correct | 5 ms | 1024 KB | Output is correct |

17 | Correct | 5 ms | 1024 KB | Output is correct |

18 | Correct | 106 ms | 105720 KB | Output is correct |

19 | Correct | 69 ms | 64248 KB | Output is correct |

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

21 | Correct | 57 ms | 60664 KB | Output is correct |

22 | Correct | 78 ms | 78560 KB | Output is correct |

23 | Correct | 26 ms | 29312 KB | Output is correct |

24 | Correct | 20 ms | 23040 KB | Output is correct |

25 | Correct | 25 ms | 28672 KB | Output is correct |

26 | Correct | 11 ms | 11136 KB | Output is correct |

27 | Correct | 27 ms | 29952 KB | Output is correct |

28 | Correct | 19 ms | 21376 KB | Output is correct |

29 | Correct | 28 ms | 30592 KB | Output is correct |

30 | Correct | 21 ms | 24192 KB | Output is correct |

31 | Correct | 26 ms | 28672 KB | Output is correct |

32 | Correct | 14 ms | 15232 KB | Output is correct |

33 | Correct | 25 ms | 28664 KB | Output is correct |

34 | Correct | 10 ms | 10368 KB | Output is correct |

35 | Correct | 25 ms | 28152 KB | Output is correct |

36 | Correct | 12 ms | 13440 KB | Output is correct |

37 | Correct | 26 ms | 29952 KB | Output is correct |

38 | Correct | 16 ms | 16512 KB | Output is correct |

39 | Correct | 27 ms | 31232 KB | Output is correct |

40 | Correct | 16 ms | 18432 KB | Output is correct |

41 | Correct | 148 ms | 130424 KB | Output is correct |

42 | Correct | 102 ms | 87928 KB | Output is correct |

43 | Correct | 139 ms | 130296 KB | Output is correct |

44 | Correct | 84 ms | 86904 KB | Output is correct |

45 | Correct | 141 ms | 130300 KB | Output is correct |

46 | Correct | 84 ms | 87928 KB | Output is correct |

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

1 | Correct | 5 ms | 512 KB | Output is correct |

2 | Correct | 4 ms | 512 KB | Output is correct |

3 | Correct | 5 ms | 768 KB | Output is correct |

4 | Correct | 5 ms | 512 KB | Output is correct |

5 | Correct | 5 ms | 512 KB | Output is correct |

6 | Correct | 5 ms | 896 KB | Output is correct |

7 | Correct | 5 ms | 640 KB | Output is correct |

8 | Correct | 5 ms | 768 KB | Output is correct |

9 | Correct | 6 ms | 896 KB | Output is correct |

10 | Correct | 4 ms | 384 KB | Output is correct |

11 | Correct | 6 ms | 384 KB | Output is correct |

12 | Correct | 5 ms | 896 KB | Output is correct |

13 | Correct | 13 ms | 1024 KB | Output is correct |

14 | Correct | 5 ms | 512 KB | Output is correct |

15 | Correct | 5 ms | 640 KB | Output is correct |

16 | Correct | 5 ms | 1024 KB | Output is correct |

17 | Correct | 5 ms | 1024 KB | Output is correct |

18 | Correct | 5 ms | 1152 KB | Output is correct |

19 | Correct | 5 ms | 768 KB | Output is correct |

20 | Correct | 5 ms | 1024 KB | Output is correct |

21 | Correct | 5 ms | 1152 KB | Output is correct |

22 | Correct | 5 ms | 768 KB | Output is correct |

23 | Correct | 5 ms | 1280 KB | Output is correct |

24 | Correct | 5 ms | 1024 KB | Output is correct |

25 | Correct | 5 ms | 1152 KB | Output is correct |

26 | Correct | 5 ms | 1152 KB | Output is correct |

27 | Correct | 5 ms | 640 KB | Output is correct |

28 | Correct | 5 ms | 768 KB | Output is correct |

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

30 | Correct | 5 ms | 1280 KB | Output is correct |

31 | Correct | 5 ms | 1152 KB | Output is correct |

32 | Correct | 5 ms | 1024 KB | Output is correct |

33 | Correct | 5 ms | 1280 KB | Output is correct |

34 | Correct | 5 ms | 1280 KB | Output is correct |

35 | Correct | 5 ms | 1280 KB | Output is correct |

36 | Correct | 106 ms | 105720 KB | Output is correct |

37 | Correct | 69 ms | 64248 KB | Output is correct |

38 | Correct | 29 ms | 34432 KB | Output is correct |

39 | Correct | 57 ms | 60664 KB | Output is correct |

40 | Correct | 78 ms | 78560 KB | Output is correct |

41 | Correct | 26 ms | 29312 KB | Output is correct |

42 | Correct | 20 ms | 23040 KB | Output is correct |

43 | Correct | 25 ms | 28672 KB | Output is correct |

44 | Correct | 11 ms | 11136 KB | Output is correct |

45 | Correct | 27 ms | 29952 KB | Output is correct |

46 | Correct | 19 ms | 21376 KB | Output is correct |

47 | Correct | 28 ms | 30592 KB | Output is correct |

48 | Correct | 21 ms | 24192 KB | Output is correct |

49 | Correct | 26 ms | 28672 KB | Output is correct |

50 | Correct | 14 ms | 15232 KB | Output is correct |

51 | Correct | 25 ms | 28664 KB | Output is correct |

52 | Correct | 10 ms | 10368 KB | Output is correct |

53 | Correct | 25 ms | 28152 KB | Output is correct |

54 | Correct | 12 ms | 13440 KB | Output is correct |

55 | Correct | 26 ms | 29952 KB | Output is correct |

56 | Correct | 16 ms | 16512 KB | Output is correct |

57 | Correct | 27 ms | 31232 KB | Output is correct |

58 | Correct | 16 ms | 18432 KB | Output is correct |

59 | Correct | 148 ms | 130424 KB | Output is correct |

60 | Correct | 102 ms | 87928 KB | Output is correct |

61 | Correct | 139 ms | 130296 KB | Output is correct |

62 | Correct | 84 ms | 86904 KB | Output is correct |

63 | Correct | 141 ms | 130300 KB | Output is correct |

64 | Correct | 84 ms | 87928 KB | Output is correct |

65 | Correct | 127 ms | 117624 KB | Output is correct |

66 | Correct | 121 ms | 108024 KB | Output is correct |

67 | Correct | 105 ms | 103416 KB | Output is correct |

68 | Correct | 99 ms | 95424 KB | Output is correct |

69 | Correct | 122 ms | 116472 KB | Output is correct |

70 | Correct | 116 ms | 111592 KB | Output is correct |

71 | Correct | 113 ms | 112760 KB | Output is correct |

72 | Correct | 130 ms | 114044 KB | Output is correct |

73 | Correct | 105 ms | 105720 KB | Output is correct |

74 | Correct | 99 ms | 98808 KB | Output is correct |

75 | Correct | 109 ms | 109176 KB | Output is correct |

76 | Correct | 138 ms | 125176 KB | Output is correct |

77 | Correct | 127 ms | 125176 KB | Output is correct |

78 | Correct | 100 ms | 96560 KB | Output is correct |

79 | Correct | 101 ms | 99964 KB | Output is correct |

80 | Correct | 132 ms | 122616 KB | Output is correct |

81 | Correct | 103 ms | 101116 KB | Output is correct |

82 | Correct | 111 ms | 106872 KB | Output is correct |

83 | Correct | 137 ms | 130296 KB | Output is correct |

84 | Correct | 113 ms | 111608 KB | Output is correct |

85 | Correct | 135 ms | 121440 KB | Output is correct |

86 | Correct | 121 ms | 118904 KB | Output is correct |

87 | Correct | 119 ms | 109176 KB | Output is correct |

88 | Correct | 150 ms | 131532 KB | Output is correct |

89 | Correct | 146 ms | 131748 KB | Output is correct |

90 | Correct | 113 ms | 110456 KB | Output is correct |

91 | Correct | 152 ms | 131576 KB | Output is correct |

92 | Correct | 150 ms | 131576 KB | Output is correct |

93 | Correct | 149 ms | 129144 KB | Output is correct |