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

201937 | 2020-02-12T21:16:13 Z | Osama_Alkhodairy | Collecting Stamps 3 (JOI20_ho_t3) | C++17 | 167 ms | 135544 KB |

#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long const int N = 205; int n, L; ll dp[N][N][2][N]; vector <int> x, t; void minimize(ll &x, ll y){ x = min(x, y); } int pos(int l, int r, int dir){ if(dir == 0) return l; return r; } int dist(int l, int r, int dir){ l = x[l]; r = x[r]; if(dir == 0){ if(r <= l) return l - r; return l + L - r; } if(l <= r) return r - l; return L - l + r; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); for(int l = 0 ; l < N ; l++){ for(int r = 0 ; r < N ; r++){ for(int dir = 0 ; dir < 2 ; dir++){ for(int ans = 0 ; ans < N ; ans++){ dp[l][r][dir][ans] = 1e18; } } } } cin >> n >> L; x.resize(n); for(auto &i : x) cin >> i; t.resize(n); for(auto &i : t) cin >> i; x.insert(x.begin(), 0); t.insert(t.begin(), 0); n++; dp[0][0][0][0] = dp[0][0][1][0] = 0; for(int len = 0 ; len < n - 1 ; len++){ for(int l = 0 ; l < n ; l++){ int r = (l + len) % n; if(l != 0 && l <= r) continue; int pre = (l - 1 + n) % n; int nex = (r + 1) % n; for(int dir = 0 ; dir < 2 ; dir++){ for(int ans = 0 ; ans <= len ; ans++){ ll d = dist(pos(l, r, dir), pre, 0) + dp[l][r][dir][ans]; minimize(dp[pre][r][0][ans + (d <= t[pre])], d); d = dist(pos(l, r, dir), nex, 1) + dp[l][r][dir][ans]; minimize(dp[l][nex][1][ans + (d <= t[nex])], d); } } } } int res = 0; for(int l = 0 ; l < n ; l++){ for(int r = 0 ; r < n ; r++){ for(int dir = 0 ; dir < 2 ; dir++){ for(int ans = 0 ; ans < n ; ans++){ if(dp[l][r][dir][ans] != 1e18){ res = max(res, ans); } } } } } cout << res << endl; }

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

1 | Correct | 73 ms | 135160 KB | Output is correct |

2 | Correct | 75 ms | 135160 KB | Output is correct |

3 | Correct | 75 ms | 135160 KB | Output is correct |

4 | Correct | 76 ms | 135164 KB | Output is correct |

5 | Correct | 76 ms | 135288 KB | Output is correct |

6 | Correct | 76 ms | 135160 KB | Output is correct |

7 | Correct | 75 ms | 135160 KB | Output is correct |

8 | Correct | 73 ms | 135160 KB | Output is correct |

9 | Correct | 77 ms | 135288 KB | Output is correct |

10 | Correct | 80 ms | 135164 KB | Output is correct |

11 | Correct | 75 ms | 135160 KB | Output is correct |

12 | Correct | 74 ms | 135160 KB | Output is correct |

13 | Correct | 73 ms | 135152 KB | Output is correct |

14 | Correct | 77 ms | 135288 KB | Output is correct |

15 | Correct | 79 ms | 135160 KB | Output is correct |

16 | Correct | 80 ms | 135160 KB | Output is correct |

17 | Correct | 75 ms | 135160 KB | Output is correct |

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

1 | Correct | 73 ms | 135160 KB | Output is correct |

2 | Correct | 75 ms | 135160 KB | Output is correct |

3 | Correct | 75 ms | 135160 KB | Output is correct |

4 | Correct | 76 ms | 135164 KB | Output is correct |

5 | Correct | 76 ms | 135288 KB | Output is correct |

6 | Correct | 76 ms | 135160 KB | Output is correct |

7 | Correct | 75 ms | 135160 KB | Output is correct |

8 | Correct | 73 ms | 135160 KB | Output is correct |

9 | Correct | 77 ms | 135288 KB | Output is correct |

10 | Correct | 80 ms | 135164 KB | Output is correct |

11 | Correct | 75 ms | 135160 KB | Output is correct |

12 | Correct | 74 ms | 135160 KB | Output is correct |

13 | Correct | 73 ms | 135152 KB | Output is correct |

14 | Correct | 77 ms | 135288 KB | Output is correct |

15 | Correct | 79 ms | 135160 KB | Output is correct |

16 | Correct | 80 ms | 135160 KB | Output is correct |

17 | Correct | 75 ms | 135160 KB | Output is correct |

18 | Correct | 75 ms | 135164 KB | Output is correct |

19 | Correct | 75 ms | 135288 KB | Output is correct |

20 | Correct | 75 ms | 135252 KB | Output is correct |

21 | Correct | 76 ms | 135160 KB | Output is correct |

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

23 | Correct | 77 ms | 135160 KB | Output is correct |

24 | Correct | 77 ms | 135160 KB | Output is correct |

25 | Correct | 74 ms | 135160 KB | Output is correct |

26 | Correct | 76 ms | 135160 KB | Output is correct |

27 | Correct | 75 ms | 135164 KB | Output is correct |

28 | Correct | 76 ms | 135160 KB | Output is correct |

29 | Correct | 75 ms | 135160 KB | Output is correct |

30 | Correct | 73 ms | 135160 KB | Output is correct |

31 | Correct | 74 ms | 135160 KB | Output is correct |

32 | Correct | 72 ms | 135160 KB | Output is correct |

33 | Correct | 74 ms | 135160 KB | Output is correct |

34 | Correct | 79 ms | 135416 KB | Output is correct |

35 | Correct | 75 ms | 135160 KB | Output is correct |

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

1 | Correct | 73 ms | 135160 KB | Output is correct |

2 | Correct | 75 ms | 135160 KB | Output is correct |

3 | Correct | 75 ms | 135160 KB | Output is correct |

4 | Correct | 76 ms | 135164 KB | Output is correct |

5 | Correct | 76 ms | 135288 KB | Output is correct |

6 | Correct | 76 ms | 135160 KB | Output is correct |

7 | Correct | 75 ms | 135160 KB | Output is correct |

8 | Correct | 73 ms | 135160 KB | Output is correct |

9 | Correct | 77 ms | 135288 KB | Output is correct |

10 | Correct | 80 ms | 135164 KB | Output is correct |

11 | Correct | 75 ms | 135160 KB | Output is correct |

12 | Correct | 74 ms | 135160 KB | Output is correct |

13 | Correct | 73 ms | 135152 KB | Output is correct |

14 | Correct | 77 ms | 135288 KB | Output is correct |

15 | Correct | 79 ms | 135160 KB | Output is correct |

16 | Correct | 80 ms | 135160 KB | Output is correct |

17 | Correct | 75 ms | 135160 KB | Output is correct |

18 | Correct | 135 ms | 135160 KB | Output is correct |

19 | Correct | 107 ms | 135160 KB | Output is correct |

20 | Correct | 90 ms | 135160 KB | Output is correct |

21 | Correct | 104 ms | 135160 KB | Output is correct |

22 | Correct | 117 ms | 135160 KB | Output is correct |

23 | Correct | 88 ms | 135160 KB | Output is correct |

24 | Correct | 84 ms | 135160 KB | Output is correct |

25 | Correct | 85 ms | 135288 KB | Output is correct |

26 | Correct | 77 ms | 135164 KB | Output is correct |

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

28 | Correct | 84 ms | 135160 KB | Output is correct |

29 | Correct | 85 ms | 135288 KB | Output is correct |

30 | Correct | 85 ms | 135160 KB | Output is correct |

31 | Correct | 87 ms | 135288 KB | Output is correct |

32 | Correct | 80 ms | 135160 KB | Output is correct |

33 | Correct | 86 ms | 135160 KB | Output is correct |

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

35 | Correct | 87 ms | 135288 KB | Output is correct |

36 | Correct | 78 ms | 135160 KB | Output is correct |

37 | Correct | 88 ms | 135160 KB | Output is correct |

38 | Correct | 81 ms | 135160 KB | Output is correct |

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

40 | Correct | 82 ms | 135288 KB | Output is correct |

41 | Correct | 167 ms | 135288 KB | Output is correct |

42 | Correct | 121 ms | 135160 KB | Output is correct |

43 | Correct | 149 ms | 135160 KB | Output is correct |

44 | Correct | 124 ms | 135288 KB | Output is correct |

45 | Correct | 151 ms | 135160 KB | Output is correct |

46 | Correct | 112 ms | 135160 KB | Output is correct |

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

1 | Correct | 73 ms | 135160 KB | Output is correct |

2 | Correct | 75 ms | 135160 KB | Output is correct |

3 | Correct | 75 ms | 135160 KB | Output is correct |

4 | Correct | 76 ms | 135164 KB | Output is correct |

5 | Correct | 76 ms | 135288 KB | Output is correct |

6 | Correct | 76 ms | 135160 KB | Output is correct |

7 | Correct | 75 ms | 135160 KB | Output is correct |

8 | Correct | 73 ms | 135160 KB | Output is correct |

9 | Correct | 77 ms | 135288 KB | Output is correct |

10 | Correct | 80 ms | 135164 KB | Output is correct |

11 | Correct | 75 ms | 135160 KB | Output is correct |

12 | Correct | 74 ms | 135160 KB | Output is correct |

13 | Correct | 73 ms | 135152 KB | Output is correct |

14 | Correct | 77 ms | 135288 KB | Output is correct |

15 | Correct | 79 ms | 135160 KB | Output is correct |

16 | Correct | 80 ms | 135160 KB | Output is correct |

17 | Correct | 75 ms | 135160 KB | Output is correct |

18 | Correct | 75 ms | 135164 KB | Output is correct |

19 | Correct | 75 ms | 135288 KB | Output is correct |

20 | Correct | 75 ms | 135252 KB | Output is correct |

21 | Correct | 76 ms | 135160 KB | Output is correct |

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

23 | Correct | 77 ms | 135160 KB | Output is correct |

24 | Correct | 77 ms | 135160 KB | Output is correct |

25 | Correct | 74 ms | 135160 KB | Output is correct |

26 | Correct | 76 ms | 135160 KB | Output is correct |

27 | Correct | 75 ms | 135164 KB | Output is correct |

28 | Correct | 76 ms | 135160 KB | Output is correct |

29 | Correct | 75 ms | 135160 KB | Output is correct |

30 | Correct | 73 ms | 135160 KB | Output is correct |

31 | Correct | 74 ms | 135160 KB | Output is correct |

32 | Correct | 72 ms | 135160 KB | Output is correct |

33 | Correct | 74 ms | 135160 KB | Output is correct |

34 | Correct | 79 ms | 135416 KB | Output is correct |

35 | Correct | 75 ms | 135160 KB | Output is correct |

36 | Correct | 135 ms | 135160 KB | Output is correct |

37 | Correct | 107 ms | 135160 KB | Output is correct |

38 | Correct | 90 ms | 135160 KB | Output is correct |

39 | Correct | 104 ms | 135160 KB | Output is correct |

40 | Correct | 117 ms | 135160 KB | Output is correct |

41 | Correct | 88 ms | 135160 KB | Output is correct |

42 | Correct | 84 ms | 135160 KB | Output is correct |

43 | Correct | 85 ms | 135288 KB | Output is correct |

44 | Correct | 77 ms | 135164 KB | Output is correct |

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

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

47 | Correct | 85 ms | 135288 KB | Output is correct |

48 | Correct | 85 ms | 135160 KB | Output is correct |

49 | Correct | 87 ms | 135288 KB | Output is correct |

50 | Correct | 80 ms | 135160 KB | Output is correct |

51 | Correct | 86 ms | 135160 KB | Output is correct |

52 | Correct | 78 ms | 135288 KB | Output is correct |

53 | Correct | 87 ms | 135288 KB | Output is correct |

54 | Correct | 78 ms | 135160 KB | Output is correct |

55 | Correct | 88 ms | 135160 KB | Output is correct |

56 | Correct | 81 ms | 135160 KB | Output is correct |

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

58 | Correct | 82 ms | 135288 KB | Output is correct |

59 | Correct | 167 ms | 135288 KB | Output is correct |

60 | Correct | 121 ms | 135160 KB | Output is correct |

61 | Correct | 149 ms | 135160 KB | Output is correct |

62 | Correct | 124 ms | 135288 KB | Output is correct |

63 | Correct | 151 ms | 135160 KB | Output is correct |

64 | Correct | 112 ms | 135160 KB | Output is correct |

65 | Correct | 150 ms | 135160 KB | Output is correct |

66 | Correct | 142 ms | 135544 KB | Output is correct |

67 | Correct | 135 ms | 135160 KB | Output is correct |

68 | Correct | 117 ms | 135160 KB | Output is correct |

69 | Correct | 144 ms | 135160 KB | Output is correct |

70 | Correct | 151 ms | 135408 KB | Output is correct |

71 | Correct | 144 ms | 135160 KB | Output is correct |

72 | Correct | 143 ms | 135160 KB | Output is correct |

73 | Correct | 139 ms | 135160 KB | Output is correct |

74 | Correct | 131 ms | 135160 KB | Output is correct |

75 | Correct | 141 ms | 135160 KB | Output is correct |

76 | Correct | 155 ms | 135220 KB | Output is correct |

77 | Correct | 154 ms | 135160 KB | Output is correct |

78 | Correct | 129 ms | 135416 KB | Output is correct |

79 | Correct | 131 ms | 135160 KB | Output is correct |

80 | Correct | 150 ms | 135260 KB | Output is correct |

81 | Correct | 133 ms | 135160 KB | Output is correct |

82 | Correct | 139 ms | 135288 KB | Output is correct |

83 | Correct | 161 ms | 135160 KB | Output is correct |

84 | Correct | 145 ms | 135260 KB | Output is correct |

85 | Correct | 152 ms | 135288 KB | Output is correct |

86 | Correct | 147 ms | 135160 KB | Output is correct |

87 | Correct | 125 ms | 135160 KB | Output is correct |

88 | Correct | 163 ms | 135160 KB | Output is correct |

89 | Correct | 165 ms | 135288 KB | Output is correct |

90 | Correct | 141 ms | 135160 KB | Output is correct |

91 | Correct | 163 ms | 135160 KB | Output is correct |

92 | Correct | 164 ms | 135160 KB | Output is correct |

93 | Correct | 162 ms | 135160 KB | Output is correct |