# | 제출 시각^{} |
아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|

253276 | 2020-07-27T15:13:33 Z | doowey | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 1363 ms | 152300 KB |

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); struct State{ ll dist; int to_left; int to_right; int collect; int side; bool operator< (const State &Q) const { return dist > Q.dist; } }; const int N = 201; const ll inf = (ll)1e18; ll dp[N][N][N][2]; ll x[N], t[N]; priority_queue<State> bf; void upd_state(State nx){ if(nx.dist < dp[nx.to_left][nx.to_right][nx.collect][nx.side]){ dp[nx.to_left][nx.to_right][nx.collect][nx.side] = nx.dist; bf.push(nx); } } int main(){ fastIO; int n; ll d; cin >> n >> d; for(int i = 1 ; i <= n; i ++ ){ cin >> x[i]; } for(int i = 1; i <= n; i ++ ){ cin >> t[i]; } for(int i = 0 ; i <= n; i ++ ){ for(int j = 0 ; j <= n; j ++ ){ for(int k = 0; k <= n; k ++ ){ for(int b = 0; b < 2; b ++ ){ dp[i][j][k][b] = inf; } } } } int m = (n + 1); x[m]=d,t[m]=0; x[0]=0,t[0]=0; int ans = 0; upd_state({0, 0, 0, 0, 0}); State cur; State nx; ll dnw; while(!bf.empty()){ cur = bf.top(); bf.pop(); ans = max(ans, cur.collect); if(cur.dist != dp[cur.to_left][cur.to_right][cur.collect][cur.side]) continue; upd_state({cur.dist + x[cur.to_right] + d-x[m - cur.to_left], cur.to_left, cur.to_right, cur.collect, cur.side ^ 1}); if(cur.to_left + cur.to_right < n){ if(cur.side == 1){ nx = {cur.dist, cur.to_left, cur.to_right + 1, cur.collect, 1}; dnw = x[cur.to_right+1] - x[cur.to_right] + cur.dist; nx.dist = dnw; if(dnw <= t[cur.to_right + 1]) nx.collect ++ ; upd_state(nx); } if(cur.side == 0){ nx = {cur.dist, cur.to_left + 1, cur.to_right, cur.collect, 0}; dnw = x[m - cur.to_left]-x[m - cur.to_left - 1] + cur.dist; nx.dist = dnw; if(dnw <= t[m - cur.to_left - 1]) nx.collect ++ ; upd_state(nx); } } } cout << ans << "\n"; return 0; }

# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|

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

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

3 | Correct | 1 ms | 640 KB | Output is correct |

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

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

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

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

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

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

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

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

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

13 | Correct | 1 ms | 896 KB | Output is correct |

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

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

16 | Correct | 1 ms | 896 KB | Output is correct |

17 | Correct | 1 ms | 896 KB | Output is correct |

# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|

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

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

3 | Correct | 1 ms | 640 KB | Output is correct |

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

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

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

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

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

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

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

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

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

13 | Correct | 1 ms | 896 KB | Output is correct |

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

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

16 | Correct | 1 ms | 896 KB | Output is correct |

17 | Correct | 1 ms | 896 KB | Output is correct |

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

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

20 | Correct | 1 ms | 896 KB | Output is correct |

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

22 | Correct | 1 ms | 640 KB | Output is correct |

23 | Correct | 1 ms | 1152 KB | Output is correct |

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

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

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

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

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

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

30 | Correct | 1 ms | 1152 KB | Output is correct |

31 | Correct | 1 ms | 1024 KB | Output is correct |

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

33 | Correct | 1 ms | 1152 KB | Output is correct |

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

35 | Correct | 1 ms | 1152 KB | Output is correct |

# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|

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

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

3 | Correct | 1 ms | 640 KB | Output is correct |

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

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

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

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

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

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

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

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

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

13 | Correct | 1 ms | 896 KB | Output is correct |

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

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

16 | Correct | 1 ms | 896 KB | Output is correct |

17 | Correct | 1 ms | 896 KB | Output is correct |

18 | Correct | 688 ms | 115420 KB | Output is correct |

19 | Correct | 298 ms | 68832 KB | Output is correct |

20 | Correct | 89 ms | 36596 KB | Output is correct |

21 | Correct | 268 ms | 65356 KB | Output is correct |

22 | Correct | 506 ms | 88920 KB | Output is correct |

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

24 | Correct | 37 ms | 23920 KB | Output is correct |

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

26 | Correct | 16 ms | 11200 KB | Output is correct |

27 | Correct | 50 ms | 30712 KB | Output is correct |

28 | Correct | 35 ms | 22392 KB | Output is correct |

29 | Correct | 73 ms | 31344 KB | Output is correct |

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

31 | Correct | 68 ms | 29572 KB | Output is correct |

32 | Correct | 30 ms | 15612 KB | Output is correct |

33 | Correct | 72 ms | 29684 KB | Output is correct |

34 | Correct | 15 ms | 10876 KB | Output is correct |

35 | Correct | 26 ms | 27804 KB | Output is correct |

36 | Correct | 17 ms | 13948 KB | Output is correct |

37 | Correct | 31 ms | 30076 KB | Output is correct |

38 | Correct | 28 ms | 16892 KB | Output is correct |

39 | Correct | 32 ms | 31100 KB | Output is correct |

40 | Correct | 26 ms | 18684 KB | Output is correct |

41 | Correct | 965 ms | 151676 KB | Output is correct |

42 | Correct | 60 ms | 86072 KB | Output is correct |

43 | Correct | 1006 ms | 151628 KB | Output is correct |

44 | Correct | 48 ms | 84920 KB | Output is correct |

45 | Correct | 910 ms | 151752 KB | Output is correct |

46 | Correct | 50 ms | 86072 KB | Output is correct |

# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|

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

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

3 | Correct | 1 ms | 640 KB | Output is correct |

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

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

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

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

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

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

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

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

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

13 | Correct | 1 ms | 896 KB | Output is correct |

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

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

16 | Correct | 1 ms | 896 KB | Output is correct |

17 | Correct | 1 ms | 896 KB | Output is correct |

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

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

20 | Correct | 1 ms | 896 KB | Output is correct |

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

22 | Correct | 1 ms | 640 KB | Output is correct |

23 | Correct | 1 ms | 1152 KB | Output is correct |

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

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

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

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

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

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

30 | Correct | 1 ms | 1152 KB | Output is correct |

31 | Correct | 1 ms | 1024 KB | Output is correct |

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

33 | Correct | 1 ms | 1152 KB | Output is correct |

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

35 | Correct | 1 ms | 1152 KB | Output is correct |

36 | Correct | 688 ms | 115420 KB | Output is correct |

37 | Correct | 298 ms | 68832 KB | Output is correct |

38 | Correct | 89 ms | 36596 KB | Output is correct |

39 | Correct | 268 ms | 65356 KB | Output is correct |

40 | Correct | 506 ms | 88920 KB | Output is correct |

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

42 | Correct | 37 ms | 23920 KB | Output is correct |

43 | Correct | 43 ms | 29552 KB | Output is correct |

44 | Correct | 16 ms | 11200 KB | Output is correct |

45 | Correct | 50 ms | 30712 KB | Output is correct |

46 | Correct | 35 ms | 22392 KB | Output is correct |

47 | Correct | 73 ms | 31344 KB | Output is correct |

48 | Correct | 43 ms | 24952 KB | Output is correct |

49 | Correct | 68 ms | 29572 KB | Output is correct |

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

51 | Correct | 72 ms | 29684 KB | Output is correct |

52 | Correct | 15 ms | 10876 KB | Output is correct |

53 | Correct | 26 ms | 27804 KB | Output is correct |

54 | Correct | 17 ms | 13948 KB | Output is correct |

55 | Correct | 31 ms | 30076 KB | Output is correct |

56 | Correct | 28 ms | 16892 KB | Output is correct |

57 | Correct | 32 ms | 31100 KB | Output is correct |

58 | Correct | 26 ms | 18684 KB | Output is correct |

59 | Correct | 965 ms | 151676 KB | Output is correct |

60 | Correct | 60 ms | 86072 KB | Output is correct |

61 | Correct | 1006 ms | 151628 KB | Output is correct |

62 | Correct | 48 ms | 84920 KB | Output is correct |

63 | Correct | 910 ms | 151752 KB | Output is correct |

64 | Correct | 50 ms | 86072 KB | Output is correct |

65 | Correct | 1172 ms | 139676 KB | Output is correct |

66 | Correct | 941 ms | 117748 KB | Output is correct |

67 | Correct | 685 ms | 113112 KB | Output is correct |

68 | Correct | 693 ms | 105480 KB | Output is correct |

69 | Correct | 1153 ms | 138312 KB | Output is correct |

70 | Correct | 422 ms | 121168 KB | Output is correct |

71 | Correct | 1062 ms | 134732 KB | Output is correct |

72 | Correct | 461 ms | 123612 KB | Output is correct |

73 | Correct | 512 ms | 115416 KB | Output is correct |

74 | Correct | 363 ms | 102496 KB | Output is correct |

75 | Correct | 810 ms | 131400 KB | Output is correct |

76 | Correct | 686 ms | 134488 KB | Output is correct |

77 | Correct | 1237 ms | 146760 KB | Output is correct |

78 | Correct | 394 ms | 106592 KB | Output is correct |

79 | Correct | 906 ms | 122184 KB | Output is correct |

80 | Correct | 753 ms | 131928 KB | Output is correct |

81 | Correct | 805 ms | 123208 KB | Output is correct |

82 | Correct | 392 ms | 110432 KB | Output is correct |

83 | Correct | 1240 ms | 151752 KB | Output is correct |

84 | Correct | 393 ms | 115044 KB | Output is correct |

85 | Correct | 682 ms | 143048 KB | Output is correct |

86 | Correct | 474 ms | 128348 KB | Output is correct |

87 | Correct | 898 ms | 131284 KB | Output is correct |

88 | Correct | 1185 ms | 152260 KB | Output is correct |

89 | Correct | 1363 ms | 152300 KB | Output is correct |

90 | Correct | 63 ms | 108088 KB | Output is correct |

91 | Correct | 1353 ms | 152264 KB | Output is correct |

92 | Correct | 1142 ms | 152264 KB | Output is correct |

93 | Correct | 84 ms | 126264 KB | Output is correct |