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

1106882 | 2024-10-31T08:33:35 Z | pit4h | Catfish Farm (IOI22_fish) | C++17 | 114 ms | 29540 KB |

#include "fish.h" #include<bits/stdc++.h> using namespace std; using ll=long long; using pi=pair<int,int>; using vi=vector<int>; #define mp make_pair #define eb emplace_back #define x first #define y second #define sz(x)int((x).size()) #define all(x)(x).begin(),(x).end() #define rep(i,a,b)for(int i=(a);i<(b);i++) #define per(i,a,b)for(int i=(b)-1;i>=(a);i--) bool ckmin(auto&a,auto b){return b<a?a=b,1:0;} bool ckmax(auto&a,auto b){return b>a?a=b,1:0;} #ifdef LOCAL auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.x<<", "<<p.y<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto&e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X); #else #define debug(...){} #endif struct Container { ll shift=0,best=0; void add(ll delta) { shift += delta; best += delta; } void ins(ll v) { ckmax(best, v); } ll get() { return best; } }; long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { vector<vector<pi>> sweep(N + 2); rep(i,0,M) { sweep[X[i]+1].eb(Y[i],W[i]); } rep(i,0,N+2) { sweep[i].eb(N,0); sort(all(sweep[i])); } vector<vector<ll>> dp(N+2); vector<ll> best_dp(N+2); rep(i,0,N+2) { dp[i].resize(sz(sweep[i])); } ll ans = 0; rep(i,1,N+1) { debug(i); int ptr_l=0,ptr_r=0; ll sum_l=0,sum_cur=0,sum_r=0; Container best_l; rep(j,0,sz(sweep[i])) { auto [y,w] = sweep[i][j]; while (ptr_l < sz(sweep[i-1]) && sweep[i-1][ptr_l].x < y) { sum_l+=sweep[i-1][ptr_l].y; best_l.ins(dp[i-1][ptr_l]); best_l.add(sweep[i-1][ptr_l].y); ptr_l++; } while (ptr_r < sz(sweep[i+1]) && sweep[i+1][ptr_r].x < y) { sum_r+=sweep[i+1][ptr_r].y; ptr_r++; } ckmax(dp[i][j], best_l.get()); ckmax(dp[i+1][ptr_r], best_l.get() + sum_r); // cur takes from left and right ckmax(dp[i+1][ptr_r], best_dp[i-1] + sum_r); // prev does not take any from column i ckmax(dp[i+1][ptr_r], best_dp[i] + sum_r - sum_cur); // prev takes unlimited amount from column i sum_cur+=w; } rep(s,0,2) { rep(j,0,sz(sweep[i+s])) { ckmax(best_dp[i+s], dp[i+s][j]); } } debug(dp); } rep(i,0,N+2) { rep(j,0,sz(dp[i])) { ckmax(ans, dp[i][j]); } } return ans; }

### Compilation message

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

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

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

3 | Correct | 14 ms | 12112 KB | Output is correct |

4 | Correct | 14 ms | 12112 KB | Output is correct |

5 | Correct | 103 ms | 23728 KB | Output is correct |

6 | Correct | 114 ms | 23912 KB | Output is correct |

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

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

2 | Correct | 57 ms | 17172 KB | Output is correct |

3 | Correct | 78 ms | 19796 KB | Output is correct |

4 | Correct | 34 ms | 14012 KB | Output is correct |

5 | Correct | 43 ms | 16060 KB | Output is correct |

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

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

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

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

10 | Correct | 16 ms | 12112 KB | Output is correct |

11 | Correct | 13 ms | 12112 KB | Output is correct |

12 | Correct | 31 ms | 14208 KB | Output is correct |

13 | Correct | 49 ms | 16056 KB | Output is correct |

14 | Correct | 32 ms | 14216 KB | Output is correct |

15 | Correct | 43 ms | 15548 KB | Output is correct |

16 | Correct | 32 ms | 14020 KB | Output is correct |

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

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

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

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

3 | Correct | 24 ms | 12112 KB | Output is correct |

4 | Correct | 22 ms | 13648 KB | Output is correct |

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

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

7 | Correct | 36 ms | 15944 KB | Output is correct |

8 | Correct | 39 ms | 15888 KB | Output is correct |

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

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

2 | Correct | 0 ms | 336 KB | Output is correct |

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

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

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

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

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

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

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

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

11 | Correct | 1 ms | 336 KB | Output is correct |

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

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

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

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

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

2 | Correct | 0 ms | 336 KB | Output is correct |

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

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

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

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

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

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

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

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

11 | Correct | 1 ms | 336 KB | Output is correct |

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

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

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

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

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

17 | Correct | 16 ms | 3016 KB | Output is correct |

18 | Correct | 13 ms | 3152 KB | Output is correct |

19 | Correct | 13 ms | 3152 KB | Output is correct |

20 | Correct | 12 ms | 3268 KB | Output is correct |

21 | Correct | 12 ms | 3152 KB | Output is correct |

22 | Correct | 24 ms | 5968 KB | Output is correct |

23 | Correct | 5 ms | 848 KB | Output is correct |

24 | Correct | 8 ms | 2176 KB | Output is correct |

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

26 | Correct | 3 ms | 1012 KB | Output is correct |

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

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

2 | Correct | 0 ms | 336 KB | Output is correct |

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

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

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

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

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

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

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

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

11 | Correct | 1 ms | 336 KB | Output is correct |

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

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

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

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

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

17 | Correct | 16 ms | 3016 KB | Output is correct |

18 | Correct | 13 ms | 3152 KB | Output is correct |

19 | Correct | 13 ms | 3152 KB | Output is correct |

20 | Correct | 12 ms | 3268 KB | Output is correct |

21 | Correct | 12 ms | 3152 KB | Output is correct |

22 | Correct | 24 ms | 5968 KB | Output is correct |

23 | Correct | 5 ms | 848 KB | Output is correct |

24 | Correct | 8 ms | 2176 KB | Output is correct |

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

26 | Correct | 3 ms | 1012 KB | Output is correct |

27 | Correct | 2 ms | 848 KB | Output is correct |

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

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

30 | Correct | 80 ms | 18760 KB | Output is correct |

31 | Correct | 90 ms | 18912 KB | Output is correct |

32 | Correct | 78 ms | 19784 KB | Output is correct |

33 | Correct | 84 ms | 18760 KB | Output is correct |

34 | Correct | 109 ms | 18760 KB | Output is correct |

35 | Correct | 31 ms | 7748 KB | Output is correct |

36 | Correct | 77 ms | 19428 KB | Output is correct |

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

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

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

3 | Correct | 24 ms | 12112 KB | Output is correct |

4 | Correct | 22 ms | 13648 KB | Output is correct |

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

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

7 | Correct | 36 ms | 15944 KB | Output is correct |

8 | Correct | 39 ms | 15888 KB | Output is correct |

9 | Correct | 34 ms | 15804 KB | Output is correct |

10 | Correct | 35 ms | 11188 KB | Output is correct |

11 | Correct | 68 ms | 22228 KB | Output is correct |

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

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

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

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

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

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

18 | Correct | 13 ms | 12112 KB | Output is correct |

19 | Correct | 13 ms | 12112 KB | Output is correct |

20 | Correct | 14 ms | 12112 KB | Output is correct |

21 | Correct | 13 ms | 12168 KB | Output is correct |

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

23 | Correct | 71 ms | 22344 KB | Output is correct |

24 | Correct | 71 ms | 22856 KB | Output is correct |

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

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

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

3 | Correct | 14 ms | 12112 KB | Output is correct |

4 | Correct | 14 ms | 12112 KB | Output is correct |

5 | Correct | 103 ms | 23728 KB | Output is correct |

6 | Correct | 114 ms | 23912 KB | Output is correct |

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

8 | Correct | 57 ms | 17172 KB | Output is correct |

9 | Correct | 78 ms | 19796 KB | Output is correct |

10 | Correct | 34 ms | 14012 KB | Output is correct |

11 | Correct | 43 ms | 16060 KB | Output is correct |

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

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

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

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

16 | Correct | 16 ms | 12112 KB | Output is correct |

17 | Correct | 13 ms | 12112 KB | Output is correct |

18 | Correct | 31 ms | 14208 KB | Output is correct |

19 | Correct | 49 ms | 16056 KB | Output is correct |

20 | Correct | 32 ms | 14216 KB | Output is correct |

21 | Correct | 43 ms | 15548 KB | Output is correct |

22 | Correct | 32 ms | 14020 KB | Output is correct |

23 | Correct | 36 ms | 15544 KB | Output is correct |

24 | Correct | 13 ms | 12280 KB | Output is correct |

25 | Correct | 16 ms | 12112 KB | Output is correct |

26 | Correct | 24 ms | 12112 KB | Output is correct |

27 | Correct | 22 ms | 13648 KB | Output is correct |

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

29 | Correct | 35 ms | 15436 KB | Output is correct |

30 | Correct | 36 ms | 15944 KB | Output is correct |

31 | Correct | 39 ms | 15888 KB | Output is correct |

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

33 | Correct | 0 ms | 336 KB | Output is correct |

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

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

36 | Correct | 1 ms | 336 KB | Output is correct |

37 | Correct | 1 ms | 336 KB | Output is correct |

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

39 | Correct | 1 ms | 336 KB | Output is correct |

40 | Correct | 1 ms | 336 KB | Output is correct |

41 | Correct | 1 ms | 592 KB | Output is correct |

42 | Correct | 1 ms | 336 KB | Output is correct |

43 | Correct | 1 ms | 336 KB | Output is correct |

44 | Correct | 1 ms | 336 KB | Output is correct |

45 | Correct | 1 ms | 592 KB | Output is correct |

46 | Correct | 1 ms | 336 KB | Output is correct |

47 | Correct | 1 ms | 336 KB | Output is correct |

48 | Correct | 16 ms | 3016 KB | Output is correct |

49 | Correct | 13 ms | 3152 KB | Output is correct |

50 | Correct | 13 ms | 3152 KB | Output is correct |

51 | Correct | 12 ms | 3268 KB | Output is correct |

52 | Correct | 12 ms | 3152 KB | Output is correct |

53 | Correct | 24 ms | 5968 KB | Output is correct |

54 | Correct | 5 ms | 848 KB | Output is correct |

55 | Correct | 8 ms | 2176 KB | Output is correct |

56 | Correct | 1 ms | 336 KB | Output is correct |

57 | Correct | 3 ms | 1012 KB | Output is correct |

58 | Correct | 2 ms | 848 KB | Output is correct |

59 | Correct | 56 ms | 13952 KB | Output is correct |

60 | Correct | 79 ms | 19280 KB | Output is correct |

61 | Correct | 80 ms | 18760 KB | Output is correct |

62 | Correct | 90 ms | 18912 KB | Output is correct |

63 | Correct | 78 ms | 19784 KB | Output is correct |

64 | Correct | 84 ms | 18760 KB | Output is correct |

65 | Correct | 109 ms | 18760 KB | Output is correct |

66 | Correct | 31 ms | 7748 KB | Output is correct |

67 | Correct | 77 ms | 19428 KB | Output is correct |

68 | Correct | 34 ms | 15804 KB | Output is correct |

69 | Correct | 35 ms | 11188 KB | Output is correct |

70 | Correct | 68 ms | 22228 KB | Output is correct |

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

72 | Correct | 1 ms | 336 KB | Output is correct |

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

74 | Correct | 1 ms | 336 KB | Output is correct |

75 | Correct | 1 ms | 336 KB | Output is correct |

76 | Correct | 1 ms | 336 KB | Output is correct |

77 | Correct | 13 ms | 12112 KB | Output is correct |

78 | Correct | 13 ms | 12112 KB | Output is correct |

79 | Correct | 14 ms | 12112 KB | Output is correct |

80 | Correct | 13 ms | 12168 KB | Output is correct |

81 | Correct | 52 ms | 16948 KB | Output is correct |

82 | Correct | 71 ms | 22344 KB | Output is correct |

83 | Correct | 71 ms | 22856 KB | Output is correct |

84 | Correct | 96 ms | 28968 KB | Output is correct |

85 | Correct | 110 ms | 29436 KB | Output is correct |

86 | Correct | 111 ms | 28228 KB | Output is correct |

87 | Correct | 114 ms | 29264 KB | Output is correct |

88 | Correct | 1 ms | 336 KB | Output is correct |

89 | Correct | 111 ms | 29404 KB | Output is correct |

90 | Correct | 98 ms | 29284 KB | Output is correct |

91 | Correct | 89 ms | 29540 KB | Output is correct |