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

230117 | 2020-05-08T13:08:42 Z | AMO5 | Collecting Stamps 3 (JOI20_ho_t3) | C++ | 318 ms | 509816 KB |

// READ & UNDERSTAND // ll, int overflow, array bounds, memset(0) // special cases (n=1?), n+1 (1-index) // do smth instead of nothing & stay organized // WRITE STUFF DOWN #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define all(x) (x).begin(), (x).end() #define MOD 1000000007 typedef long long ll; typedef pair <int, int> ii; typedef pair <ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef long double ld; ll INF=LLONG_MAX; int const mxn=404; int dp[mxn][mxn][mxn][2]; //le,ri,cnt,where int x[mxn],t[mxn],n,L; int dist(int a, int b){ if(a>b)swap(a,b); return min(b-a,L-(b-a)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); cin >> n >> L; for(int i=0; i<n; i++){ cin >> x[i]; x[i+n+1] = x[i]; } for(int i=0; i<n; i++){ cin >> t[i]; t[i+n+1] = t[i]; } for(int i=0; i<=2*n; i++) for(int j=0; j<=2*n; j++) for(int k=0; k<=n; k++) for(int l=0; l<2; l++) dp[i][j][k][l]=1e9+1; int ans = 0; dp[n][n][0][0]=0; for(int len=0; len<=n; len++){ for(int i=n-len; i<=n; i++){ int j=i+len; for(int k=0; k<=n; k++){ for(int l=0; l<2; l++){ if(dp[i][j][k][l]>1e9)continue; int pos=(l==0?i:j); ans=max(ans,k); if(k==n)continue; //left if(i){ int cur=dp[i][j][k][l]+dist(x[pos],x[i-1]); dp[i-1][j][k+(cur<=t[i-1])][0]=min(dp[i-1][j][k+(cur<=t[i-1])][0],cur); } //right if(j<2*n){ int cur=dp[i][j][k][l]+dist(x[pos],x[j+1]); dp[i][j+1][k+(cur<=t[j+1])][1]=min(dp[i][j+1][k+(cur<=t[j+1])][1],cur); } } } } } cout << ans << endl; }

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

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

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

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

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

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

6 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

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

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

12 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

16 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

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

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

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

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

6 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

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

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

12 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

16 | Correct | 6 ms | 2432 KB | Output is correct |

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

18 | Correct | 6 ms | 3072 KB | Output is correct |

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

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

21 | Correct | 6 ms | 3072 KB | Output is correct |

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

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

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

25 | Correct | 6 ms | 3072 KB | Output is correct |

26 | Correct | 6 ms | 3072 KB | Output is correct |

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

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

29 | Correct | 6 ms | 3456 KB | Output is correct |

30 | Correct | 6 ms | 3456 KB | Output is correct |

31 | Correct | 6 ms | 3072 KB | Output is correct |

32 | Correct | 6 ms | 2688 KB | Output is correct |

33 | Correct | 6 ms | 3456 KB | Output is correct |

34 | Correct | 6 ms | 3456 KB | Output is correct |

35 | Correct | 6 ms | 3456 KB | Output is correct |

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

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

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

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

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

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

6 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

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

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

12 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

16 | Correct | 6 ms | 2432 KB | Output is correct |

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

18 | Correct | 242 ms | 408824 KB | Output is correct |

19 | Correct | 143 ms | 247288 KB | Output is correct |

20 | Correct | 73 ms | 131192 KB | Output is correct |

21 | Correct | 130 ms | 233336 KB | Output is correct |

22 | Correct | 174 ms | 303096 KB | Output is correct |

23 | Correct | 65 ms | 111480 KB | Output is correct |

24 | Correct | 48 ms | 86912 KB | Output is correct |

25 | Correct | 65 ms | 109048 KB | Output is correct |

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

27 | Correct | 68 ms | 113844 KB | Output is correct |

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

29 | Correct | 68 ms | 116220 KB | Output is correct |

30 | Correct | 52 ms | 91128 KB | Output is correct |

31 | Correct | 64 ms | 109048 KB | Output is correct |

32 | Correct | 33 ms | 56704 KB | Output is correct |

33 | Correct | 63 ms | 109048 KB | Output is correct |

34 | Correct | 23 ms | 38272 KB | Output is correct |

35 | Correct | 58 ms | 106744 KB | Output is correct |

36 | Correct | 29 ms | 50168 KB | Output is correct |

37 | Correct | 61 ms | 113912 KB | Output is correct |

38 | Correct | 35 ms | 61824 KB | Output is correct |

39 | Correct | 63 ms | 118648 KB | Output is correct |

40 | Correct | 39 ms | 69112 KB | Output is correct |

41 | Correct | 314 ms | 504720 KB | Output is correct |

42 | Correct | 173 ms | 339320 KB | Output is correct |

43 | Correct | 318 ms | 504696 KB | Output is correct |

44 | Correct | 169 ms | 335224 KB | Output is correct |

45 | Correct | 312 ms | 504696 KB | Output is correct |

46 | Correct | 173 ms | 339320 KB | Output is correct |

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

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

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

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

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

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

6 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

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

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

12 | Correct | 6 ms | 2432 KB | Output is correct |

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

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

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

16 | Correct | 6 ms | 2432 KB | Output is correct |

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

18 | Correct | 6 ms | 3072 KB | Output is correct |

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

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

21 | Correct | 6 ms | 3072 KB | Output is correct |

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

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

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

25 | Correct | 6 ms | 3072 KB | Output is correct |

26 | Correct | 6 ms | 3072 KB | Output is correct |

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

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

29 | Correct | 6 ms | 3456 KB | Output is correct |

30 | Correct | 6 ms | 3456 KB | Output is correct |

31 | Correct | 6 ms | 3072 KB | Output is correct |

32 | Correct | 6 ms | 2688 KB | Output is correct |

33 | Correct | 6 ms | 3456 KB | Output is correct |

34 | Correct | 6 ms | 3456 KB | Output is correct |

35 | Correct | 6 ms | 3456 KB | Output is correct |

36 | Correct | 242 ms | 408824 KB | Output is correct |

37 | Correct | 143 ms | 247288 KB | Output is correct |

38 | Correct | 73 ms | 131192 KB | Output is correct |

39 | Correct | 130 ms | 233336 KB | Output is correct |

40 | Correct | 174 ms | 303096 KB | Output is correct |

41 | Correct | 65 ms | 111480 KB | Output is correct |

42 | Correct | 48 ms | 86912 KB | Output is correct |

43 | Correct | 65 ms | 109048 KB | Output is correct |

44 | Correct | 25 ms | 41088 KB | Output is correct |

45 | Correct | 68 ms | 113844 KB | Output is correct |

46 | Correct | 47 ms | 80768 KB | Output is correct |

47 | Correct | 68 ms | 116220 KB | Output is correct |

48 | Correct | 52 ms | 91128 KB | Output is correct |

49 | Correct | 64 ms | 109048 KB | Output is correct |

50 | Correct | 33 ms | 56704 KB | Output is correct |

51 | Correct | 63 ms | 109048 KB | Output is correct |

52 | Correct | 23 ms | 38272 KB | Output is correct |

53 | Correct | 58 ms | 106744 KB | Output is correct |

54 | Correct | 29 ms | 50168 KB | Output is correct |

55 | Correct | 61 ms | 113912 KB | Output is correct |

56 | Correct | 35 ms | 61824 KB | Output is correct |

57 | Correct | 63 ms | 118648 KB | Output is correct |

58 | Correct | 39 ms | 69112 KB | Output is correct |

59 | Correct | 314 ms | 504720 KB | Output is correct |

60 | Correct | 173 ms | 339320 KB | Output is correct |

61 | Correct | 318 ms | 504696 KB | Output is correct |

62 | Correct | 169 ms | 335224 KB | Output is correct |

63 | Correct | 312 ms | 504696 KB | Output is correct |

64 | Correct | 173 ms | 339320 KB | Output is correct |

65 | Correct | 244 ms | 455544 KB | Output is correct |

66 | Correct | 223 ms | 417912 KB | Output is correct |

67 | Correct | 218 ms | 399736 KB | Output is correct |

68 | Correct | 191 ms | 368888 KB | Output is correct |

69 | Correct | 232 ms | 450732 KB | Output is correct |

70 | Correct | 229 ms | 431864 KB | Output is correct |

71 | Correct | 230 ms | 436496 KB | Output is correct |

72 | Correct | 243 ms | 441208 KB | Output is correct |

73 | Correct | 221 ms | 408844 KB | Output is correct |

74 | Correct | 205 ms | 381928 KB | Output is correct |

75 | Correct | 223 ms | 422520 KB | Output is correct |

76 | Correct | 298 ms | 484856 KB | Output is correct |

77 | Correct | 254 ms | 484728 KB | Output is correct |

78 | Correct | 225 ms | 373368 KB | Output is correct |

79 | Correct | 201 ms | 386424 KB | Output is correct |

80 | Correct | 298 ms | 474872 KB | Output is correct |

81 | Correct | 205 ms | 390776 KB | Output is correct |

82 | Correct | 239 ms | 413432 KB | Output is correct |

83 | Correct | 267 ms | 504680 KB | Output is correct |

84 | Correct | 247 ms | 431864 KB | Output is correct |

85 | Correct | 269 ms | 470008 KB | Output is correct |

86 | Correct | 267 ms | 460280 KB | Output is correct |

87 | Correct | 223 ms | 422648 KB | Output is correct |

88 | Correct | 277 ms | 509816 KB | Output is correct |

89 | Correct | 257 ms | 509816 KB | Output is correct |

90 | Correct | 226 ms | 427128 KB | Output is correct |

91 | Correct | 277 ms | 509816 KB | Output is correct |

92 | Correct | 269 ms | 509816 KB | Output is correct |

93 | Correct | 264 ms | 499704 KB | Output is correct |