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

203432 | 2020-02-20T15:45:40 Z | mraron | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 831 ms | 127612 KB |

#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,L; ll x[201], t[201]; ll dp[201][201][2][201]; int dist(int i, int j) { return min(abs(x[i]-x[j]), L-abs(x[i]-x[j])); } //mikor elég legkésőbb kezdeni ll solve(int l, int r, int side, int cnt) { if(cnt==0) return 1LL<<60; if(l>r) { return -1LL<<60; } //cerr<<l<<" "<<r<<" "<<side<<" "<<cnt<<"\n"; if(dp[l][r][side][cnt]!=-1) return dp[l][r][side][cnt]; int akt; if(side==0) akt=l-1; else akt=r+1; ll ans=-1LL<<60; ans=max(ans, solve(l+1,r,0,cnt)-dist(l,akt)); ans=max(ans, min(t[l],solve(l+1,r,0,cnt-1))-dist(l,akt)); ans=max(ans, solve(l,r-1,1,cnt)-dist(r,akt)); ans=max(ans, min(t[r], solve(l,r-1,1,cnt-1))-dist(r,akt)); return dp[l][r][side][cnt]=ans; } int main() { cin>>n>>L; for(int i=0;i<n;++i) cin>>x[i]; for(int i=0;i<n;++i) cin>>t[i]; memset(dp,-1,sizeof dp); int ans=0; for(int i=0;i<=n;i++) { //cerr<<i<<": "<<solve(0,n-1,1,i)<<"\n"; if(solve(0,n-1,1,i)>=0) ans=i; } cout<<ans<<"\n"; return 0; }

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

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

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

3 | Correct | 71 ms | 127480 KB | Output is correct |

4 | Correct | 72 ms | 127480 KB | Output is correct |

5 | Correct | 72 ms | 127480 KB | Output is correct |

6 | Correct | 77 ms | 127480 KB | Output is correct |

7 | Correct | 74 ms | 127528 KB | Output is correct |

8 | Correct | 71 ms | 127480 KB | Output is correct |

9 | Correct | 74 ms | 127480 KB | Output is correct |

10 | Correct | 73 ms | 127352 KB | Output is correct |

11 | Correct | 76 ms | 127608 KB | Output is correct |

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

13 | Correct | 72 ms | 127480 KB | Output is correct |

14 | Correct | 70 ms | 127480 KB | Output is correct |

15 | Correct | 70 ms | 127480 KB | Output is correct |

16 | Correct | 72 ms | 127480 KB | Output is correct |

17 | Correct | 71 ms | 127484 KB | Output is correct |

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

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

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

3 | Correct | 71 ms | 127480 KB | Output is correct |

4 | Correct | 72 ms | 127480 KB | Output is correct |

5 | Correct | 72 ms | 127480 KB | Output is correct |

6 | Correct | 77 ms | 127480 KB | Output is correct |

7 | Correct | 74 ms | 127528 KB | Output is correct |

8 | Correct | 71 ms | 127480 KB | Output is correct |

9 | Correct | 74 ms | 127480 KB | Output is correct |

10 | Correct | 73 ms | 127352 KB | Output is correct |

11 | Correct | 76 ms | 127608 KB | Output is correct |

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

13 | Correct | 72 ms | 127480 KB | Output is correct |

14 | Correct | 70 ms | 127480 KB | Output is correct |

15 | Correct | 70 ms | 127480 KB | Output is correct |

16 | Correct | 72 ms | 127480 KB | Output is correct |

17 | Correct | 71 ms | 127484 KB | Output is correct |

18 | Correct | 74 ms | 127480 KB | Output is correct |

19 | Correct | 72 ms | 127480 KB | Output is correct |

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

21 | Correct | 72 ms | 127480 KB | Output is correct |

22 | Correct | 74 ms | 127480 KB | Output is correct |

23 | Correct | 75 ms | 127480 KB | Output is correct |

24 | Correct | 74 ms | 127480 KB | Output is correct |

25 | Correct | 71 ms | 127480 KB | Output is correct |

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

27 | Correct | 72 ms | 127480 KB | Output is correct |

28 | Correct | 73 ms | 127480 KB | Output is correct |

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

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

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

32 | Correct | 73 ms | 127480 KB | Output is correct |

33 | Correct | 73 ms | 127480 KB | Output is correct |

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

35 | Correct | 72 ms | 127480 KB | Output is correct |

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

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

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

3 | Correct | 71 ms | 127480 KB | Output is correct |

4 | Correct | 72 ms | 127480 KB | Output is correct |

5 | Correct | 72 ms | 127480 KB | Output is correct |

6 | Correct | 77 ms | 127480 KB | Output is correct |

7 | Correct | 74 ms | 127528 KB | Output is correct |

8 | Correct | 71 ms | 127480 KB | Output is correct |

9 | Correct | 74 ms | 127480 KB | Output is correct |

10 | Correct | 73 ms | 127352 KB | Output is correct |

11 | Correct | 76 ms | 127608 KB | Output is correct |

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

13 | Correct | 72 ms | 127480 KB | Output is correct |

14 | Correct | 70 ms | 127480 KB | Output is correct |

15 | Correct | 70 ms | 127480 KB | Output is correct |

16 | Correct | 72 ms | 127480 KB | Output is correct |

17 | Correct | 71 ms | 127484 KB | Output is correct |

18 | Correct | 427 ms | 127608 KB | Output is correct |

19 | Correct | 193 ms | 127480 KB | Output is correct |

20 | Correct | 136 ms | 127480 KB | Output is correct |

21 | Correct | 185 ms | 127608 KB | Output is correct |

22 | Correct | 242 ms | 127556 KB | Output is correct |

23 | Correct | 104 ms | 127480 KB | Output is correct |

24 | Correct | 95 ms | 127480 KB | Output is correct |

25 | Correct | 109 ms | 127496 KB | Output is correct |

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

27 | Correct | 107 ms | 127532 KB | Output is correct |

28 | Correct | 94 ms | 127480 KB | Output is correct |

29 | Correct | 107 ms | 127480 KB | Output is correct |

30 | Correct | 104 ms | 127608 KB | Output is correct |

31 | Correct | 105 ms | 127480 KB | Output is correct |

32 | Correct | 89 ms | 127480 KB | Output is correct |

33 | Correct | 108 ms | 127480 KB | Output is correct |

34 | Correct | 77 ms | 127492 KB | Output is correct |

35 | Correct | 113 ms | 127600 KB | Output is correct |

36 | Correct | 84 ms | 127480 KB | Output is correct |

37 | Correct | 109 ms | 127484 KB | Output is correct |

38 | Correct | 87 ms | 127480 KB | Output is correct |

39 | Correct | 111 ms | 127484 KB | Output is correct |

40 | Correct | 91 ms | 127608 KB | Output is correct |

41 | Correct | 647 ms | 127480 KB | Output is correct |

42 | Correct | 292 ms | 127480 KB | Output is correct |

43 | Correct | 693 ms | 127608 KB | Output is correct |

44 | Correct | 269 ms | 127480 KB | Output is correct |

45 | Correct | 712 ms | 127608 KB | Output is correct |

46 | Correct | 282 ms | 127480 KB | Output is correct |

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

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

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

3 | Correct | 71 ms | 127480 KB | Output is correct |

4 | Correct | 72 ms | 127480 KB | Output is correct |

5 | Correct | 72 ms | 127480 KB | Output is correct |

6 | Correct | 77 ms | 127480 KB | Output is correct |

7 | Correct | 74 ms | 127528 KB | Output is correct |

8 | Correct | 71 ms | 127480 KB | Output is correct |

9 | Correct | 74 ms | 127480 KB | Output is correct |

10 | Correct | 73 ms | 127352 KB | Output is correct |

11 | Correct | 76 ms | 127608 KB | Output is correct |

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

13 | Correct | 72 ms | 127480 KB | Output is correct |

14 | Correct | 70 ms | 127480 KB | Output is correct |

15 | Correct | 70 ms | 127480 KB | Output is correct |

16 | Correct | 72 ms | 127480 KB | Output is correct |

17 | Correct | 71 ms | 127484 KB | Output is correct |

18 | Correct | 74 ms | 127480 KB | Output is correct |

19 | Correct | 72 ms | 127480 KB | Output is correct |

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

21 | Correct | 72 ms | 127480 KB | Output is correct |

22 | Correct | 74 ms | 127480 KB | Output is correct |

23 | Correct | 75 ms | 127480 KB | Output is correct |

24 | Correct | 74 ms | 127480 KB | Output is correct |

25 | Correct | 71 ms | 127480 KB | Output is correct |

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

27 | Correct | 72 ms | 127480 KB | Output is correct |

28 | Correct | 73 ms | 127480 KB | Output is correct |

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

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

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

32 | Correct | 73 ms | 127480 KB | Output is correct |

33 | Correct | 73 ms | 127480 KB | Output is correct |

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

35 | Correct | 72 ms | 127480 KB | Output is correct |

36 | Correct | 427 ms | 127608 KB | Output is correct |

37 | Correct | 193 ms | 127480 KB | Output is correct |

38 | Correct | 136 ms | 127480 KB | Output is correct |

39 | Correct | 185 ms | 127608 KB | Output is correct |

40 | Correct | 242 ms | 127556 KB | Output is correct |

41 | Correct | 104 ms | 127480 KB | Output is correct |

42 | Correct | 95 ms | 127480 KB | Output is correct |

43 | Correct | 109 ms | 127496 KB | Output is correct |

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

45 | Correct | 107 ms | 127532 KB | Output is correct |

46 | Correct | 94 ms | 127480 KB | Output is correct |

47 | Correct | 107 ms | 127480 KB | Output is correct |

48 | Correct | 104 ms | 127608 KB | Output is correct |

49 | Correct | 105 ms | 127480 KB | Output is correct |

50 | Correct | 89 ms | 127480 KB | Output is correct |

51 | Correct | 108 ms | 127480 KB | Output is correct |

52 | Correct | 77 ms | 127492 KB | Output is correct |

53 | Correct | 113 ms | 127600 KB | Output is correct |

54 | Correct | 84 ms | 127480 KB | Output is correct |

55 | Correct | 109 ms | 127484 KB | Output is correct |

56 | Correct | 87 ms | 127480 KB | Output is correct |

57 | Correct | 111 ms | 127484 KB | Output is correct |

58 | Correct | 91 ms | 127608 KB | Output is correct |

59 | Correct | 647 ms | 127480 KB | Output is correct |

60 | Correct | 292 ms | 127480 KB | Output is correct |

61 | Correct | 693 ms | 127608 KB | Output is correct |

62 | Correct | 269 ms | 127480 KB | Output is correct |

63 | Correct | 712 ms | 127608 KB | Output is correct |

64 | Correct | 282 ms | 127480 KB | Output is correct |

65 | Correct | 536 ms | 127608 KB | Output is correct |

66 | Correct | 402 ms | 127480 KB | Output is correct |

67 | Correct | 397 ms | 127608 KB | Output is correct |

68 | Correct | 314 ms | 127480 KB | Output is correct |

69 | Correct | 562 ms | 127508 KB | Output is correct |

70 | Correct | 489 ms | 127608 KB | Output is correct |

71 | Correct | 484 ms | 127480 KB | Output is correct |

72 | Correct | 491 ms | 127608 KB | Output is correct |

73 | Correct | 410 ms | 127480 KB | Output is correct |

74 | Correct | 376 ms | 127504 KB | Output is correct |

75 | Correct | 416 ms | 127480 KB | Output is correct |

76 | Correct | 643 ms | 127608 KB | Output is correct |

77 | Correct | 660 ms | 127608 KB | Output is correct |

78 | Correct | 344 ms | 127480 KB | Output is correct |

79 | Correct | 403 ms | 127608 KB | Output is correct |

80 | Correct | 606 ms | 127480 KB | Output is correct |

81 | Correct | 406 ms | 127480 KB | Output is correct |

82 | Correct | 429 ms | 127612 KB | Output is correct |

83 | Correct | 646 ms | 127480 KB | Output is correct |

84 | Correct | 499 ms | 127512 KB | Output is correct |

85 | Correct | 623 ms | 127608 KB | Output is correct |

86 | Correct | 568 ms | 127480 KB | Output is correct |

87 | Correct | 450 ms | 127608 KB | Output is correct |

88 | Correct | 720 ms | 127608 KB | Output is correct |

89 | Correct | 735 ms | 127608 KB | Output is correct |

90 | Correct | 428 ms | 127484 KB | Output is correct |

91 | Correct | 730 ms | 127608 KB | Output is correct |

92 | Correct | 831 ms | 127608 KB | Output is correct |

93 | Correct | 711 ms | 127608 KB | Output is correct |