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

202628 | 2020-02-17T11:28:51 Z | SamAnd | Collecting Stamps 3 (JOI20_ho_t3) | C++17 | 150 ms | 129576 KB |

#include <bits/stdc++.h> using namespace std; const int N = 202; const long long INF = 1000000009000000009; int n, L; int x[N], t[N]; int ans; long long dp[N][N][2][N]; int dist1(int x, int y) { if (y <= x) return (x - y); return L - (y - x); } int dist2(int x, int y) { if (y >= x) return (y - x); return L - (x - y); } int main() { //freopen("input.txt", "r", stdin); 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]); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { for (int z = 0; z < 2; ++z) { for (int k = 0; k < N; ++k) { dp[i][j][z][k] = INF; } } } } dp[0][0][0][0] = dp[0][0][1][0] = 0; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n; ++j) { for (int z = 0; z < 2; ++z) { for (int k = 0; k <= n; ++k) { if (dp[i][j][z][k] == INF) continue; ans = max(ans, k); if (z == 0) { if (i + 1 + j <= n) { int v = (n - i + 1) % (n + 1); int u = (n - (i + 1) + 1) % (n + 1); if (dp[i][j][z][k] + dist1(x[v], x[u]) <= t[u]) dp[i + 1][j][z][k + 1] = min(dp[i + 1][j][z][k + 1], dp[i][j][z][k] + dist1(x[v], x[u])); else dp[i + 1][j][z][k] = min(dp[i + 1][j][z][k], dp[i][j][z][k] + dist1(x[v], x[u])); } if (i + j + 1 <= n) { int v = (n - i + 1) % (n + 1); int u = j + 1; if (dp[i][j][z][k] + dist2(x[v], x[u]) <= t[u]) dp[i][j + 1][(z ^ 1)][k + 1] = min(dp[i][j + 1][(z ^ 1)][k + 1], dp[i][j][z][k] + dist2(x[v], x[u])); else dp[i][j + 1][(z ^ 1)][k] = min(dp[i][j + 1][(z ^ 1)][k], dp[i][j][z][k] + dist2(x[v], x[u])); } } else { if (i + j + 1 <= n) { int v = j; int u = j + 1; if (dp[i][j][z][k] + dist2(x[v], x[u]) <= t[u]) dp[i][j + 1][z][k + 1] = min(dp[i][j + 1][z][k + 1], dp[i][j][z][k] + dist2(x[v], x[u])); else dp[i][j + 1][z][k] = min(dp[i][j + 1][z][k], dp[i][j][z][k] + dist2(x[v], x[u])); } if (i + 1 + j <= n) { int v = j; int u = (n - (i + 1) + 1) % (n + 1); if (dp[i][j][z][k] + dist1(x[v], x[u]) <= t[u]) dp[i + 1][j][(z ^ 1)][k + 1] = min(dp[i + 1][j][(z ^ 1)][k + 1], dp[i][j][z][k] + dist1(x[v], x[u])); else dp[i + 1][j][(z ^ 1)][k] = min(dp[i + 1][j][(z ^ 1)][k], dp[i][j][z][k] + dist1(x[v], x[u])); } } } } } } printf("%d\n", ans); return 0; }

### Compilation message

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

1 | Correct | 72 ms | 129400 KB | Output is correct |

2 | Correct | 72 ms | 129304 KB | Output is correct |

3 | Correct | 76 ms | 129400 KB | Output is correct |

4 | Correct | 73 ms | 129400 KB | Output is correct |

5 | Correct | 71 ms | 129400 KB | Output is correct |

6 | Correct | 74 ms | 129528 KB | Output is correct |

7 | Correct | 72 ms | 129436 KB | Output is correct |

8 | Correct | 74 ms | 129400 KB | Output is correct |

9 | Correct | 73 ms | 129400 KB | Output is correct |

10 | Correct | 72 ms | 129400 KB | Output is correct |

11 | Correct | 72 ms | 129276 KB | Output is correct |

12 | Correct | 71 ms | 129400 KB | Output is correct |

13 | Correct | 71 ms | 129400 KB | Output is correct |

14 | Correct | 71 ms | 129400 KB | Output is correct |

15 | Correct | 74 ms | 129400 KB | Output is correct |

16 | Correct | 70 ms | 129352 KB | Output is correct |

17 | Correct | 73 ms | 129400 KB | Output is correct |

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

1 | Correct | 72 ms | 129400 KB | Output is correct |

2 | Correct | 72 ms | 129304 KB | Output is correct |

3 | Correct | 76 ms | 129400 KB | Output is correct |

4 | Correct | 73 ms | 129400 KB | Output is correct |

5 | Correct | 71 ms | 129400 KB | Output is correct |

6 | Correct | 74 ms | 129528 KB | Output is correct |

7 | Correct | 72 ms | 129436 KB | Output is correct |

8 | Correct | 74 ms | 129400 KB | Output is correct |

9 | Correct | 73 ms | 129400 KB | Output is correct |

10 | Correct | 72 ms | 129400 KB | Output is correct |

11 | Correct | 72 ms | 129276 KB | Output is correct |

12 | Correct | 71 ms | 129400 KB | Output is correct |

13 | Correct | 71 ms | 129400 KB | Output is correct |

14 | Correct | 71 ms | 129400 KB | Output is correct |

15 | Correct | 74 ms | 129400 KB | Output is correct |

16 | Correct | 70 ms | 129352 KB | Output is correct |

17 | Correct | 73 ms | 129400 KB | Output is correct |

18 | Correct | 73 ms | 129400 KB | Output is correct |

19 | Correct | 71 ms | 129400 KB | Output is correct |

20 | Correct | 72 ms | 129404 KB | Output is correct |

21 | Correct | 71 ms | 129400 KB | Output is correct |

22 | Correct | 72 ms | 129400 KB | Output is correct |

23 | Correct | 70 ms | 129400 KB | Output is correct |

24 | Correct | 73 ms | 129300 KB | Output is correct |

25 | Correct | 72 ms | 129404 KB | Output is correct |

26 | Correct | 72 ms | 129400 KB | Output is correct |

27 | Correct | 83 ms | 129400 KB | Output is correct |

28 | Correct | 81 ms | 129528 KB | Output is correct |

29 | Correct | 106 ms | 129400 KB | Output is correct |

30 | Correct | 74 ms | 129400 KB | Output is correct |

31 | Correct | 83 ms | 129400 KB | Output is correct |

32 | Correct | 71 ms | 129400 KB | Output is correct |

33 | Correct | 77 ms | 129276 KB | Output is correct |

34 | Correct | 78 ms | 129400 KB | Output is correct |

35 | Correct | 81 ms | 129400 KB | Output is correct |

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

1 | Correct | 72 ms | 129400 KB | Output is correct |

2 | Correct | 72 ms | 129304 KB | Output is correct |

3 | Correct | 76 ms | 129400 KB | Output is correct |

4 | Correct | 73 ms | 129400 KB | Output is correct |

5 | Correct | 71 ms | 129400 KB | Output is correct |

6 | Correct | 74 ms | 129528 KB | Output is correct |

7 | Correct | 72 ms | 129436 KB | Output is correct |

8 | Correct | 74 ms | 129400 KB | Output is correct |

9 | Correct | 73 ms | 129400 KB | Output is correct |

10 | Correct | 72 ms | 129400 KB | Output is correct |

11 | Correct | 72 ms | 129276 KB | Output is correct |

12 | Correct | 71 ms | 129400 KB | Output is correct |

13 | Correct | 71 ms | 129400 KB | Output is correct |

14 | Correct | 71 ms | 129400 KB | Output is correct |

15 | Correct | 74 ms | 129400 KB | Output is correct |

16 | Correct | 70 ms | 129352 KB | Output is correct |

17 | Correct | 73 ms | 129400 KB | Output is correct |

18 | Correct | 131 ms | 129340 KB | Output is correct |

19 | Correct | 114 ms | 129576 KB | Output is correct |

20 | Correct | 83 ms | 129396 KB | Output is correct |

21 | Correct | 93 ms | 129400 KB | Output is correct |

22 | Correct | 113 ms | 129408 KB | Output is correct |

23 | Correct | 83 ms | 129376 KB | Output is correct |

24 | Correct | 82 ms | 129400 KB | Output is correct |

25 | Correct | 84 ms | 129400 KB | Output is correct |

26 | Correct | 79 ms | 129376 KB | Output is correct |

27 | Correct | 84 ms | 129400 KB | Output is correct |

28 | Correct | 81 ms | 129400 KB | Output is correct |

29 | Correct | 82 ms | 129320 KB | Output is correct |

30 | Correct | 81 ms | 129400 KB | Output is correct |

31 | Correct | 78 ms | 129400 KB | Output is correct |

32 | Correct | 75 ms | 129400 KB | Output is correct |

33 | Correct | 94 ms | 129400 KB | Output is correct |

34 | Correct | 73 ms | 129400 KB | Output is correct |

35 | Correct | 78 ms | 129400 KB | Output is correct |

36 | Correct | 73 ms | 129400 KB | Output is correct |

37 | Correct | 78 ms | 129400 KB | Output is correct |

38 | Correct | 82 ms | 129400 KB | Output is correct |

39 | Correct | 87 ms | 129404 KB | Output is correct |

40 | Correct | 77 ms | 129400 KB | Output is correct |

41 | Correct | 134 ms | 129400 KB | Output is correct |

42 | Correct | 89 ms | 129400 KB | Output is correct |

43 | Correct | 124 ms | 129400 KB | Output is correct |

44 | Correct | 89 ms | 129400 KB | Output is correct |

45 | Correct | 132 ms | 129400 KB | Output is correct |

46 | Correct | 85 ms | 129400 KB | Output is correct |

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

1 | Correct | 72 ms | 129400 KB | Output is correct |

2 | Correct | 72 ms | 129304 KB | Output is correct |

3 | Correct | 76 ms | 129400 KB | Output is correct |

4 | Correct | 73 ms | 129400 KB | Output is correct |

5 | Correct | 71 ms | 129400 KB | Output is correct |

6 | Correct | 74 ms | 129528 KB | Output is correct |

7 | Correct | 72 ms | 129436 KB | Output is correct |

8 | Correct | 74 ms | 129400 KB | Output is correct |

9 | Correct | 73 ms | 129400 KB | Output is correct |

10 | Correct | 72 ms | 129400 KB | Output is correct |

11 | Correct | 72 ms | 129276 KB | Output is correct |

12 | Correct | 71 ms | 129400 KB | Output is correct |

13 | Correct | 71 ms | 129400 KB | Output is correct |

14 | Correct | 71 ms | 129400 KB | Output is correct |

15 | Correct | 74 ms | 129400 KB | Output is correct |

16 | Correct | 70 ms | 129352 KB | Output is correct |

17 | Correct | 73 ms | 129400 KB | Output is correct |

18 | Correct | 73 ms | 129400 KB | Output is correct |

19 | Correct | 71 ms | 129400 KB | Output is correct |

20 | Correct | 72 ms | 129404 KB | Output is correct |

21 | Correct | 71 ms | 129400 KB | Output is correct |

22 | Correct | 72 ms | 129400 KB | Output is correct |

23 | Correct | 70 ms | 129400 KB | Output is correct |

24 | Correct | 73 ms | 129300 KB | Output is correct |

25 | Correct | 72 ms | 129404 KB | Output is correct |

26 | Correct | 72 ms | 129400 KB | Output is correct |

27 | Correct | 83 ms | 129400 KB | Output is correct |

28 | Correct | 81 ms | 129528 KB | Output is correct |

29 | Correct | 106 ms | 129400 KB | Output is correct |

30 | Correct | 74 ms | 129400 KB | Output is correct |

31 | Correct | 83 ms | 129400 KB | Output is correct |

32 | Correct | 71 ms | 129400 KB | Output is correct |

33 | Correct | 77 ms | 129276 KB | Output is correct |

34 | Correct | 78 ms | 129400 KB | Output is correct |

35 | Correct | 81 ms | 129400 KB | Output is correct |

36 | Correct | 131 ms | 129340 KB | Output is correct |

37 | Correct | 114 ms | 129576 KB | Output is correct |

38 | Correct | 83 ms | 129396 KB | Output is correct |

39 | Correct | 93 ms | 129400 KB | Output is correct |

40 | Correct | 113 ms | 129408 KB | Output is correct |

41 | Correct | 83 ms | 129376 KB | Output is correct |

42 | Correct | 82 ms | 129400 KB | Output is correct |

43 | Correct | 84 ms | 129400 KB | Output is correct |

44 | Correct | 79 ms | 129376 KB | Output is correct |

45 | Correct | 84 ms | 129400 KB | Output is correct |

46 | Correct | 81 ms | 129400 KB | Output is correct |

47 | Correct | 82 ms | 129320 KB | Output is correct |

48 | Correct | 81 ms | 129400 KB | Output is correct |

49 | Correct | 78 ms | 129400 KB | Output is correct |

50 | Correct | 75 ms | 129400 KB | Output is correct |

51 | Correct | 94 ms | 129400 KB | Output is correct |

52 | Correct | 73 ms | 129400 KB | Output is correct |

53 | Correct | 78 ms | 129400 KB | Output is correct |

54 | Correct | 73 ms | 129400 KB | Output is correct |

55 | Correct | 78 ms | 129400 KB | Output is correct |

56 | Correct | 82 ms | 129400 KB | Output is correct |

57 | Correct | 87 ms | 129404 KB | Output is correct |

58 | Correct | 77 ms | 129400 KB | Output is correct |

59 | Correct | 134 ms | 129400 KB | Output is correct |

60 | Correct | 89 ms | 129400 KB | Output is correct |

61 | Correct | 124 ms | 129400 KB | Output is correct |

62 | Correct | 89 ms | 129400 KB | Output is correct |

63 | Correct | 132 ms | 129400 KB | Output is correct |

64 | Correct | 85 ms | 129400 KB | Output is correct |

65 | Correct | 118 ms | 129400 KB | Output is correct |

66 | Correct | 110 ms | 129372 KB | Output is correct |

67 | Correct | 108 ms | 129400 KB | Output is correct |

68 | Correct | 106 ms | 129400 KB | Output is correct |

69 | Correct | 120 ms | 129308 KB | Output is correct |

70 | Correct | 127 ms | 129488 KB | Output is correct |

71 | Correct | 112 ms | 129400 KB | Output is correct |

72 | Correct | 122 ms | 129400 KB | Output is correct |

73 | Correct | 107 ms | 129400 KB | Output is correct |

74 | Correct | 119 ms | 129400 KB | Output is correct |

75 | Correct | 112 ms | 129528 KB | Output is correct |

76 | Correct | 134 ms | 129528 KB | Output is correct |

77 | Correct | 128 ms | 129376 KB | Output is correct |

78 | Correct | 109 ms | 129400 KB | Output is correct |

79 | Correct | 117 ms | 129400 KB | Output is correct |

80 | Correct | 127 ms | 129400 KB | Output is correct |

81 | Correct | 111 ms | 129404 KB | Output is correct |

82 | Correct | 113 ms | 129400 KB | Output is correct |

83 | Correct | 132 ms | 129400 KB | Output is correct |

84 | Correct | 110 ms | 129464 KB | Output is correct |

85 | Correct | 112 ms | 129400 KB | Output is correct |

86 | Correct | 128 ms | 129400 KB | Output is correct |

87 | Correct | 111 ms | 129400 KB | Output is correct |

88 | Correct | 145 ms | 129396 KB | Output is correct |

89 | Correct | 130 ms | 129404 KB | Output is correct |

90 | Correct | 94 ms | 129312 KB | Output is correct |

91 | Correct | 150 ms | 129400 KB | Output is correct |

92 | Correct | 129 ms | 129528 KB | Output is correct |

93 | Correct | 93 ms | 129400 KB | Output is correct |