SHARE
    TWEET
    Vince14

    custom struct comparator and constructor usage/example

    Dec 1st, 2023
    197
    0
    Never
    Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
    C++ 2.14 KB | Source Code | 0 0
    1. #include <iostream>
    2. #include <string>
    3. #include <cstring>
    4. #include <algorithm>
    5. #include <cmath>
    6. #include <vector>
    7. #include <set>
    8. #include <map>
    9. #include <stack>
    10. #include <queue>
    11. #include <deque>
    12. #include <unordered_map>
    13. #include <numeric>
    14. #include <iomanip>
    15. using namespace std;
    16. #define pii pair<long long, long long>
    17. #define ll long long
    18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
    19. #define mp(x1, x2) ( make_pair(x1, x2) )
    20. const long long dx[4] = {1, 0, 0, -1}, dy[4] = {0, 1, -1, 0};
    21. const long long dl[2] = {1, -1};
    22. const long long MOD = 100000;
    23. const long long MAXN = 2005;
    24. int n, a, b;
    25. struct cow {
    26. int p;
    27. int c;
    28. int x;
    29. cow(){
    30. p = 0;
    31. c = 0;
    32. x = 0;
    33. }
    34. cow (int p_, int c_, int x_){
    35. p = p_;
    36. c = c_;
    37. x = x_;
    38. }
    39. };
    40. vector<cow> v;
    41. int dp[MAXN][2 * MAXN];
    42. bool operator<(cow const& cx, cow const& cy){
    43. if(cx.x != cy.x) return cx.x < cy.x;
    44. return (cx.p / (double) cx.c) > (cy.p / (double) cy.c);
    45. }
    46. int main(){
    47. FAST;
    48. cin >> n >> a >> b;
    49. for(int i = 0; i < n; i++){
    50. int p, c, x;
    51. cin >> p >> c >> x;
    52. v.push_back(cow(p, c, x));
    53. }
    54. sort(v.begin(), v.end());
    55. memset(dp, -1, sizeof dp);
    56. dp[0][a + b] = 0;
    57. for(int i = 0; i < n; i++){
    58. int p = v[i].p;
    59. int c = v[i].c;
    60. int x = v[i].x;
    61. for(int j = 0; j <= a + b; j++){
    62. if(dp[i][j] == -1) continue;
    63. dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
    64. if(j >= a + c * x){
    65. dp[i + 1][j - c * x] = max(dp[i + 1][j - c * x], dp[i][j] + p);
    66. }
    67. else if(j > a){
    68. int red = (j - a) / x;
    69. if(a >= (c - red)){
    70. dp[i + 1][a - (c - red)] = max(dp[i + 1][a - (c - red)], dp[i][j] + p);
    71. }
    72. }
    73. else if(j >= c){
    74. dp[i + 1][j - c] = max(dp[i + 1][j - c], dp[i][j] + p);
    75. }
    76. }
    77. }
    78. int maxe = 0;
    79. for(int i = 0; i <= a + b; i++){
    80. maxe = max(maxe, dp[n][i]);
    81. }
    82. cout << maxe << "\n";
    83. }
    Advertisement
    Add Comment
    Please, Sign In to add comment
    Public Pastes
    We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
    Not a member of Pastebin yet?
    Sign Up, it unlocks many cool features!

    AltStyle によって変換されたページ (->オリジナル) /