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

661160 | 2022-11-24T19:16:27 Z | mychecksedad | Catfish Farm (IOI22_fish) | C++17 | 306 ms | 57308 KB |

#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define pb push_back const int N = 1e5 + 100; long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){ vector<ll> fishes[N]; vector<vector<int>> states(n + 1, {0}); for(int i = 0; i < m; ++i){ ++y[i]; for(int k = max(0, x[i] - 1); k <= min(n - 1, x[i] + 1); ++k){ states[k].pb(y[i]); } } for(int i = 0; i <= n; ++i){ sort(states[i].begin(), states[i].end()); states[i].erase(unique(states[i].begin(), states[i].end()), states[i].end()); fishes[i].resize(states[i].size()); } for(int i = 0; i < m; ++i){ int j = x[i]; int Y = lower_bound(states[j].begin(), states[j].end(), y[i]) - states[j].begin(); fishes[j][Y] += w[i]; } vector<vector<ll>> dp_up(n + 1), dp_down(n + 1); for(int i = 0; i <= n; ++i){ int sz = states[i].size(); dp_up[i].resize(sz, 0); dp_down[i].resize(sz, 0); if(i > 0){ ll best = dp_down[i - 1][0], sum = 0; for(int j = 0, left = 0; j < sz; ++j){ while(left + 1 < states[i - 1].size() && states[i - 1][left + 1] <= states[i][j]){ ++left; best += fishes[i - 1][left]; best = max(best, dp_down[i - 1][left]); } dp_down[i][j] = max(dp_down[i][j], best); } best = 0; sum = accumulate(fishes[i].begin(), fishes[i].end(), 0ll); for(int j = sz - 1, left = states[i - 1].size(); j >= 0; --j){ while(left > 0 && states[i - 1][left - 1] >= states[i][j]){ --left; best = max(best, max(dp_up[i - 1][left], dp_down[i - 1][left]) + sum); } dp_up[i][j] = max(dp_up[i][j], best - sum); sum -= fishes[i][j]; } } if(i > 1){ ll best = max(dp_down[i - 2][0], dp_up[i - 2][0]), sum = 0; for(int j = 0, left = 0, leftt = 0; j < sz; ++j){ while(leftt + 1 < states[i - 2].size() && states[i - 2][leftt + 1] <= states[i][j]){ ++leftt; while(left + 1 < states[i - 1].size() && states[i - 1][left + 1] <= states[i][j]){ ++left; sum += fishes[i - 1][left]; best += fishes[i - 1][left]; } best = max(best, max(dp_down[i - 2][leftt], dp_up[i - 2][leftt]) + sum); } dp_down[i][j] = max(dp_down[i][j], best); } best = 0; sum = accumulate(fishes[i - 1].begin(), fishes[i - 1].end(), 0ll); for(int j = sz - 1, left = states[i - 1].size(), leftt = states[i - 2].size(); j >= 0; --j){ while(leftt - 1 > 0 && states[i - 2][leftt - 1] >= states[i][j]){ --leftt; while(left - 1 > 0 && states[i - 1][left - 1] >= states[i - 2][leftt]){ --left; sum -= fishes[i - 1][left]; } best = max(best, max(dp_down[i - 2][leftt], dp_up[i - 2][leftt]) + sum); } dp_down[i][j] = max(dp_down[i][j], best); } } } return max(dp_up[n][0], dp_down[n][0]); }

### Compilation message

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

1 | Correct | 71 ms | 26480 KB | Output is correct |

2 | Correct | 85 ms | 30008 KB | Output is correct |

3 | Correct | 33 ms | 22176 KB | Output is correct |

4 | Correct | 30 ms | 22180 KB | Output is correct |

5 | Correct | 229 ms | 54076 KB | Output is correct |

6 | Correct | 289 ms | 50888 KB | Output is correct |

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

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

2 | Correct | 130 ms | 31660 KB | Output is correct |

3 | Correct | 152 ms | 35948 KB | Output is correct |

4 | Correct | 71 ms | 26480 KB | Output is correct |

5 | Correct | 85 ms | 30004 KB | Output is correct |

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

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

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

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

10 | Correct | 30 ms | 22168 KB | Output is correct |

11 | Correct | 29 ms | 22184 KB | Output is correct |

12 | Correct | 78 ms | 28760 KB | Output is correct |

13 | Correct | 100 ms | 32812 KB | Output is correct |

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

15 | Correct | 83 ms | 28604 KB | Output is correct |

16 | Correct | 77 ms | 27724 KB | Output is correct |

17 | Correct | 85 ms | 30476 KB | Output is correct |

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

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

2 | Correct | 30 ms | 22100 KB | Output is correct |

3 | Correct | 56 ms | 21428 KB | Output is correct |

4 | Correct | 50 ms | 23220 KB | Output is correct |

5 | Correct | 86 ms | 24792 KB | Output is correct |

6 | Correct | 87 ms | 24844 KB | Output is correct |

7 | Correct | 87 ms | 24792 KB | Output is correct |

8 | Correct | 85 ms | 24748 KB | Output is correct |

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

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

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

3 | Correct | 2 ms | 2644 KB | Output is correct |

4 | Correct | 2 ms | 2644 KB | Output is correct |

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

6 | Correct | 2 ms | 2644 KB | Output is correct |

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

8 | Correct | 2 ms | 2644 KB | Output is correct |

9 | Correct | 2 ms | 2644 KB | Output is correct |

10 | Correct | 3 ms | 2796 KB | Output is correct |

11 | Correct | 2 ms | 2644 KB | Output is correct |

12 | Correct | 2 ms | 2772 KB | Output is correct |

13 | Correct | 2 ms | 2660 KB | Output is correct |

14 | Correct | 2 ms | 2772 KB | Output is correct |

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

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

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

3 | Correct | 2 ms | 2644 KB | Output is correct |

4 | Correct | 2 ms | 2644 KB | Output is correct |

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

6 | Correct | 2 ms | 2644 KB | Output is correct |

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

8 | Correct | 2 ms | 2644 KB | Output is correct |

9 | Correct | 2 ms | 2644 KB | Output is correct |

10 | Correct | 3 ms | 2796 KB | Output is correct |

11 | Correct | 2 ms | 2644 KB | Output is correct |

12 | Correct | 2 ms | 2772 KB | Output is correct |

13 | Correct | 2 ms | 2660 KB | Output is correct |

14 | Correct | 2 ms | 2772 KB | Output is correct |

15 | Correct | 2 ms | 2716 KB | Output is correct |

16 | Correct | 3 ms | 2744 KB | Output is correct |

17 | Correct | 24 ms | 6708 KB | Output is correct |

18 | Correct | 24 ms | 6392 KB | Output is correct |

19 | Correct | 23 ms | 6316 KB | Output is correct |

20 | Correct | 26 ms | 6220 KB | Output is correct |

21 | Correct | 27 ms | 6196 KB | Output is correct |

22 | Correct | 52 ms | 9652 KB | Output is correct |

23 | Correct | 7 ms | 3768 KB | Output is correct |

24 | Correct | 18 ms | 5972 KB | Output is correct |

25 | Correct | 2 ms | 2744 KB | Output is correct |

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

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

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

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

3 | Correct | 2 ms | 2644 KB | Output is correct |

4 | Correct | 2 ms | 2644 KB | Output is correct |

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

6 | Correct | 2 ms | 2644 KB | Output is correct |

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

8 | Correct | 2 ms | 2644 KB | Output is correct |

9 | Correct | 2 ms | 2644 KB | Output is correct |

10 | Correct | 3 ms | 2796 KB | Output is correct |

11 | Correct | 2 ms | 2644 KB | Output is correct |

12 | Correct | 2 ms | 2772 KB | Output is correct |

13 | Correct | 2 ms | 2660 KB | Output is correct |

14 | Correct | 2 ms | 2772 KB | Output is correct |

15 | Correct | 2 ms | 2716 KB | Output is correct |

16 | Correct | 3 ms | 2744 KB | Output is correct |

17 | Correct | 24 ms | 6708 KB | Output is correct |

18 | Correct | 24 ms | 6392 KB | Output is correct |

19 | Correct | 23 ms | 6316 KB | Output is correct |

20 | Correct | 26 ms | 6220 KB | Output is correct |

21 | Correct | 27 ms | 6196 KB | Output is correct |

22 | Correct | 52 ms | 9652 KB | Output is correct |

23 | Correct | 7 ms | 3768 KB | Output is correct |

24 | Correct | 18 ms | 5972 KB | Output is correct |

25 | Correct | 2 ms | 2744 KB | Output is correct |

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

27 | Correct | 4 ms | 3412 KB | Output is correct |

28 | Correct | 116 ms | 20980 KB | Output is correct |

29 | Correct | 182 ms | 31568 KB | Output is correct |

30 | Correct | 207 ms | 42208 KB | Output is correct |

31 | Correct | 205 ms | 41932 KB | Output is correct |

32 | Correct | 172 ms | 26576 KB | Output is correct |

33 | Correct | 211 ms | 42700 KB | Output is correct |

34 | Correct | 210 ms | 42704 KB | Output is correct |

35 | Correct | 73 ms | 15732 KB | Output is correct |

36 | Correct | 194 ms | 37860 KB | Output is correct |

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

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

2 | Correct | 30 ms | 22100 KB | Output is correct |

3 | Correct | 56 ms | 21428 KB | Output is correct |

4 | Correct | 50 ms | 23220 KB | Output is correct |

5 | Correct | 86 ms | 24792 KB | Output is correct |

6 | Correct | 87 ms | 24844 KB | Output is correct |

7 | Correct | 87 ms | 24792 KB | Output is correct |

8 | Correct | 85 ms | 24748 KB | Output is correct |

9 | Correct | 99 ms | 29388 KB | Output is correct |

10 | Correct | 68 ms | 15868 KB | Output is correct |

11 | Correct | 169 ms | 29052 KB | Output is correct |

12 | Correct | 2 ms | 2644 KB | Output is correct |

13 | Correct | 2 ms | 2608 KB | Output is correct |

14 | Correct | 2 ms | 2644 KB | Output is correct |

15 | Correct | 2 ms | 2644 KB | Output is correct |

16 | Correct | 2 ms | 2600 KB | Output is correct |

17 | Correct | 2 ms | 2644 KB | Output is correct |

18 | Correct | 30 ms | 22164 KB | Output is correct |

19 | Correct | 30 ms | 22100 KB | Output is correct |

20 | Correct | 29 ms | 22156 KB | Output is correct |

21 | Correct | 33 ms | 22196 KB | Output is correct |

22 | Correct | 129 ms | 29012 KB | Output is correct |

23 | Correct | 169 ms | 34516 KB | Output is correct |

24 | Correct | 179 ms | 39148 KB | Output is correct |

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

1 | Correct | 71 ms | 26480 KB | Output is correct |

2 | Correct | 85 ms | 30008 KB | Output is correct |

3 | Correct | 33 ms | 22176 KB | Output is correct |

4 | Correct | 30 ms | 22180 KB | Output is correct |

5 | Correct | 229 ms | 54076 KB | Output is correct |

6 | Correct | 289 ms | 50888 KB | Output is correct |

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

8 | Correct | 130 ms | 31660 KB | Output is correct |

9 | Correct | 152 ms | 35948 KB | Output is correct |

10 | Correct | 71 ms | 26480 KB | Output is correct |

11 | Correct | 85 ms | 30004 KB | Output is correct |

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

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

14 | Correct | 1 ms | 2640 KB | Output is correct |

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

16 | Correct | 30 ms | 22168 KB | Output is correct |

17 | Correct | 29 ms | 22184 KB | Output is correct |

18 | Correct | 78 ms | 28760 KB | Output is correct |

19 | Correct | 100 ms | 32812 KB | Output is correct |

20 | Correct | 77 ms | 27716 KB | Output is correct |

21 | Correct | 83 ms | 28604 KB | Output is correct |

22 | Correct | 77 ms | 27724 KB | Output is correct |

23 | Correct | 85 ms | 30476 KB | Output is correct |

24 | Correct | 30 ms | 22168 KB | Output is correct |

25 | Correct | 30 ms | 22100 KB | Output is correct |

26 | Correct | 56 ms | 21428 KB | Output is correct |

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

28 | Correct | 86 ms | 24792 KB | Output is correct |

29 | Correct | 87 ms | 24844 KB | Output is correct |

30 | Correct | 87 ms | 24792 KB | Output is correct |

31 | Correct | 85 ms | 24748 KB | Output is correct |

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

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

34 | Correct | 2 ms | 2644 KB | Output is correct |

35 | Correct | 2 ms | 2644 KB | Output is correct |

36 | Correct | 2 ms | 2644 KB | Output is correct |

37 | Correct | 2 ms | 2644 KB | Output is correct |

38 | Correct | 1 ms | 2644 KB | Output is correct |

39 | Correct | 2 ms | 2644 KB | Output is correct |

40 | Correct | 2 ms | 2644 KB | Output is correct |

41 | Correct | 3 ms | 2796 KB | Output is correct |

42 | Correct | 2 ms | 2644 KB | Output is correct |

43 | Correct | 2 ms | 2772 KB | Output is correct |

44 | Correct | 2 ms | 2660 KB | Output is correct |

45 | Correct | 2 ms | 2772 KB | Output is correct |

46 | Correct | 2 ms | 2716 KB | Output is correct |

47 | Correct | 3 ms | 2744 KB | Output is correct |

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

49 | Correct | 24 ms | 6392 KB | Output is correct |

50 | Correct | 23 ms | 6316 KB | Output is correct |

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

52 | Correct | 27 ms | 6196 KB | Output is correct |

53 | Correct | 52 ms | 9652 KB | Output is correct |

54 | Correct | 7 ms | 3768 KB | Output is correct |

55 | Correct | 18 ms | 5972 KB | Output is correct |

56 | Correct | 2 ms | 2744 KB | Output is correct |

57 | Correct | 6 ms | 3668 KB | Output is correct |

58 | Correct | 4 ms | 3412 KB | Output is correct |

59 | Correct | 116 ms | 20980 KB | Output is correct |

60 | Correct | 182 ms | 31568 KB | Output is correct |

61 | Correct | 207 ms | 42208 KB | Output is correct |

62 | Correct | 205 ms | 41932 KB | Output is correct |

63 | Correct | 172 ms | 26576 KB | Output is correct |

64 | Correct | 211 ms | 42700 KB | Output is correct |

65 | Correct | 210 ms | 42704 KB | Output is correct |

66 | Correct | 73 ms | 15732 KB | Output is correct |

67 | Correct | 194 ms | 37860 KB | Output is correct |

68 | Correct | 99 ms | 29388 KB | Output is correct |

69 | Correct | 68 ms | 15868 KB | Output is correct |

70 | Correct | 169 ms | 29052 KB | Output is correct |

71 | Correct | 2 ms | 2644 KB | Output is correct |

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

73 | Correct | 2 ms | 2644 KB | Output is correct |

74 | Correct | 2 ms | 2644 KB | Output is correct |

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

76 | Correct | 2 ms | 2644 KB | Output is correct |

77 | Correct | 30 ms | 22164 KB | Output is correct |

78 | Correct | 30 ms | 22100 KB | Output is correct |

79 | Correct | 29 ms | 22156 KB | Output is correct |

80 | Correct | 33 ms | 22196 KB | Output is correct |

81 | Correct | 129 ms | 29012 KB | Output is correct |

82 | Correct | 169 ms | 34516 KB | Output is correct |

83 | Correct | 179 ms | 39148 KB | Output is correct |

84 | Correct | 262 ms | 55500 KB | Output is correct |

85 | Correct | 250 ms | 56960 KB | Output is correct |

86 | Correct | 290 ms | 55744 KB | Output is correct |

87 | Correct | 303 ms | 57292 KB | Output is correct |

88 | Correct | 2 ms | 2644 KB | Output is correct |

89 | Correct | 306 ms | 57308 KB | Output is correct |

90 | Correct | 239 ms | 53068 KB | Output is correct |

91 | Correct | 195 ms | 47420 KB | Output is correct |