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

201563 | 2020-02-11T05:57:26 Z | qkxwsm | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 147 ms | 135928 KB |

#include <bits/stdc++.h> using namespace std; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define SZ(x) ((int) (x).size()) #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; const int MAXN = 213; const int INF = 1000000007; const ll LLINF = 2696969696969696969ll; int N; ll L; pll arr[MAXN]; ll dp[MAXN][MAXN][2][MAXN]; int ans; int32_t main() { cout << fixed << setprecision(12); cerr << fixed << setprecision(4); ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> L; FOR(i, 0, N) { cin >> arr[i].fi; } FOR(i, 0, N) { cin >> arr[i].se; } arr[N] = {L, 0}; //dp[how many left we've been][how many right we've been][where are we?][# collected] = time FOR(i, 0, N + 1) { FOR(j, 0, N + 1) { FOR(k, 0, 2) { FOR(m, 0, N + 1) { dp[i][j][k][m] = LLINF; } } } } dp[0][0][1][0] = 0; FOR(i, 0, N + 1) { FOR(j, 0, N + 1 - i) { FOR(k, 0, 2) { FOR(m, 0, N + 1) { if (dp[i][j][k][m] >= LLINF) continue; ckmax(ans, m); if (i + j == N) continue; //head left. ll nt; int nm; if (k) //you are currently at arr[N - j].fi { //try to go to arr[i].fi nt = dp[i][j][k][m] + (L - arr[N - j].fi + arr[i].fi); nm = m + (nt <= arr[i].se); ckmin(dp[i + 1][j][0][nm], nt); //try to go to arr[N - j - 1].fi nt = dp[i][j][k][m] + (arr[N - j].fi - arr[N - j - 1].fi); nm = m + (nt <= arr[N - j - 1].se); ckmin(dp[i][j + 1][1][nm], nt); } else //you are currently at arr[i - 1].fi { //try to go to arr[i].fi nt = dp[i][j][k][m] + (arr[i].fi - arr[i - 1].fi); nm = m + (nt <= arr[i].se); ckmin(dp[i + 1][j][0][nm], nt); //try to go to arr[N - j - 1].fi nt = dp[i][j][k][m] + (arr[i - 1].fi + L - arr[N - j - 1].fi); nm = m + (nt <= arr[N - j - 1].se); ckmin(dp[i][j + 1][1][nm], nt); } } } } } cout << ans << '\n'; }

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

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

2 | Correct | 5 ms | 504 KB | Output is correct |

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

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

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

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

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

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

9 | Correct | 5 ms | 888 KB | Output is correct |

10 | Correct | 5 ms | 376 KB | Output is correct |

11 | Correct | 5 ms | 376 KB | Output is correct |

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

13 | Correct | 5 ms | 1016 KB | Output is correct |

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

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

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

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

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

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

2 | Correct | 5 ms | 504 KB | Output is correct |

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

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

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

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

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

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

9 | Correct | 5 ms | 888 KB | Output is correct |

10 | Correct | 5 ms | 376 KB | Output is correct |

11 | Correct | 5 ms | 376 KB | Output is correct |

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

13 | Correct | 5 ms | 1016 KB | Output is correct |

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

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

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

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

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

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

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

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

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

23 | Correct | 6 ms | 1272 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 | Correct | 5 ms | 504 KB | Output is correct |

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

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

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

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

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

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

9 | Correct | 5 ms | 888 KB | Output is correct |

10 | Correct | 5 ms | 376 KB | Output is correct |

11 | Correct | 5 ms | 376 KB | Output is correct |

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

13 | Correct | 5 ms | 1016 KB | Output is correct |

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

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

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

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

18 | Correct | 94 ms | 109048 KB | Output is correct |

19 | Correct | 55 ms | 66168 KB | Output is correct |

20 | Correct | 30 ms | 35448 KB | Output is correct |

21 | Correct | 50 ms | 62584 KB | Output is correct |

22 | Correct | 69 ms | 81016 KB | Output is correct |

23 | Correct | 27 ms | 30200 KB | Output is correct |

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

25 | Correct | 26 ms | 29560 KB | Output is correct |

26 | Correct | 12 ms | 11384 KB | Output is correct |

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

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

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

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

31 | Correct | 25 ms | 29560 KB | Output is correct |

32 | Correct | 15 ms | 15480 KB | Output is correct |

33 | Correct | 26 ms | 29560 KB | Output is correct |

34 | Correct | 11 ms | 10616 KB | Output is correct |

35 | Correct | 23 ms | 28920 KB | Output is correct |

36 | Correct | 13 ms | 13816 KB | Output is correct |

37 | Correct | 23 ms | 30840 KB | Output is correct |

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

39 | Correct | 24 ms | 32120 KB | Output is correct |

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

41 | Correct | 115 ms | 134520 KB | Output is correct |

42 | Correct | 59 ms | 90620 KB | Output is correct |

43 | Correct | 118 ms | 134520 KB | Output is correct |

44 | Correct | 61 ms | 89592 KB | Output is correct |

45 | Correct | 136 ms | 134572 KB | Output is correct |

46 | Correct | 61 ms | 90616 KB | Output is correct |

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

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

2 | Correct | 5 ms | 504 KB | Output is correct |

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

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

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

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

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

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

9 | Correct | 5 ms | 888 KB | Output is correct |

10 | Correct | 5 ms | 376 KB | Output is correct |

11 | Correct | 5 ms | 376 KB | Output is correct |

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

13 | Correct | 5 ms | 1016 KB | Output is correct |

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

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

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

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

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

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

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

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

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

23 | Correct | 6 ms | 1272 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

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

36 | Correct | 94 ms | 109048 KB | Output is correct |

37 | Correct | 55 ms | 66168 KB | Output is correct |

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

39 | Correct | 50 ms | 62584 KB | Output is correct |

40 | Correct | 69 ms | 81016 KB | Output is correct |

41 | Correct | 27 ms | 30200 KB | Output is correct |

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

43 | Correct | 26 ms | 29560 KB | Output is correct |

44 | Correct | 12 ms | 11384 KB | Output is correct |

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

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

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

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

49 | Correct | 25 ms | 29560 KB | Output is correct |

50 | Correct | 15 ms | 15480 KB | Output is correct |

51 | Correct | 26 ms | 29560 KB | Output is correct |

52 | Correct | 11 ms | 10616 KB | Output is correct |

53 | Correct | 23 ms | 28920 KB | Output is correct |

54 | Correct | 13 ms | 13816 KB | Output is correct |

55 | Correct | 23 ms | 30840 KB | Output is correct |

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

57 | Correct | 24 ms | 32120 KB | Output is correct |

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

59 | Correct | 115 ms | 134520 KB | Output is correct |

60 | Correct | 59 ms | 90620 KB | Output is correct |

61 | Correct | 118 ms | 134520 KB | Output is correct |

62 | Correct | 61 ms | 89592 KB | Output is correct |

63 | Correct | 136 ms | 134572 KB | Output is correct |

64 | Correct | 61 ms | 90616 KB | Output is correct |

65 | Correct | 102 ms | 121464 KB | Output is correct |

66 | Correct | 90 ms | 111480 KB | Output is correct |

67 | Correct | 90 ms | 106744 KB | Output is correct |

68 | Correct | 103 ms | 98680 KB | Output is correct |

69 | Correct | 110 ms | 120184 KB | Output is correct |

70 | Correct | 108 ms | 115192 KB | Output is correct |

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

72 | Correct | 111 ms | 117752 KB | Output is correct |

73 | Correct | 84 ms | 109048 KB | Output is correct |

74 | Correct | 94 ms | 102008 KB | Output is correct |

75 | Correct | 97 ms | 112760 KB | Output is correct |

76 | Correct | 119 ms | 129304 KB | Output is correct |

77 | Correct | 115 ms | 129272 KB | Output is correct |

78 | Correct | 89 ms | 99728 KB | Output is correct |

79 | Correct | 85 ms | 103160 KB | Output is correct |

80 | Correct | 114 ms | 126728 KB | Output is correct |

81 | Correct | 86 ms | 104312 KB | Output is correct |

82 | Correct | 88 ms | 110464 KB | Output is correct |

83 | Correct | 118 ms | 134520 KB | Output is correct |

84 | Correct | 91 ms | 115240 KB | Output is correct |

85 | Correct | 98 ms | 125328 KB | Output is correct |

86 | Correct | 98 ms | 122744 KB | Output is correct |

87 | Correct | 99 ms | 112760 KB | Output is correct |

88 | Correct | 134 ms | 135800 KB | Output is correct |

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

90 | Correct | 86 ms | 113912 KB | Output is correct |

91 | Correct | 147 ms | 135840 KB | Output is correct |

92 | Correct | 120 ms | 135928 KB | Output is correct |

93 | Correct | 86 ms | 133112 KB | Output is correct |