fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. struct Friend {
  6.     int p, c, x;
  7. };
  8.  
  9. int main(){
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     int N, A, B;
  14.     cin >> N >> A >> B;
  15.     vector<Friend> f(N);
  16.     for(int i = 0; i < N; i++){
  17.         cin >> f[i].p >> f[i].c >> f[i].x;
  18.     }
  19.     // sort theo x tăng dần để luôn ưu tiên dùng cones ở bạn có x nhỏ trước
  20.     sort(f.begin(), f.end(), [&](auto &a, auto &b){
  21.         return a.x < b.x;
  22.     });
  23.  
  24.     const int INF_NEG = -1e9;
  25.     // money_dp[j] = max popularity khi đã dùng hết cones, còn j mooney
  26.     // cone_dp[k]  = max popularity khi còn B mooney, còn k cones
  27.     vector<int> money_dp(A+1, INF_NEG), cone_dp(B+1, INF_NEG);
  28.     // khởi đầu: chưa mời ai, còn A mooney + B cones
  29.     money_dp[A] = 0;
  30.     cone_dp[B]  = 0;
  31.  
  32.     for(int i = 0; i < N; i++){
  33.         int Ci = f[i].c, Xi = f[i].x, Pi = f[i].p;
  34.         // mảng mới cho bước i+1
  35.         vector<int> money2(A+1, INF_NEG), cone2(B+1, INF_NEG);
  36.  
  37.         // 1) chuyển không mời bạn i
  38.         for(int j = 0; j <= A; j++){
  39.             money2[j] = max(money2[j], money_dp[j]);
  40.         }
  41.         for(int k = 0; k <= B; k++){
  42.             cone2[k] = max(cone2[k], cone_dp[k]);
  43.         }
  44.  
  45.         // 2) mời bạn i từ trạng thái đã dùng hết cones
  46.         //    => ta chỉ còn j mooney, dùng thêm Ci mooney
  47.         for(int j = 0; j <= A; j++){
  48.             if(money_dp[j] < 0) continue;
  49.             if(j >= Ci){
  50.                 money2[j - Ci] = max(money2[j - Ci], money_dp[j] + Pi);
  51.             }
  52.         }
  53.  
  54.         // 3) mời bạn i từ trạng thái còn B mooney (đang xài cones trước)
  55.         for(int k = 0; k <= B; k++){
  56.             int val = cone_dp[k];
  57.             if(val < 0) continue;
  58.             // dùng cones tối đa để giảm mooney
  59.             int use_cones = min(k, Ci * Xi);
  60.             int discount = use_cones / Xi;
  61.             int pay = Ci - discount;
  62.             if (A >= pay) {
  63.                 // sau khi mời, cones về 0, mooney còn A-pay
  64.                 cone2[k - use_cones] = max(cone2[k - use_cones], val + Pi);
  65.                 // nhưng vì sau dùng cones là k-use_cones luôn = 0 hoặc >0
  66.                 // và chúng ta chỉ cần nhớ trường hợp còn cones => cập nhật cone2[]
  67.             }
  68.             // thực ra mọi lần gọi từ cone_dp[] sau khi invite đều chuyển về cone2[]
  69.         }
  70.  
  71.         swap(money_dp, money2);
  72.         swap(cone_dp, cone2);
  73.     }
  74.  
  75.     // đáp án là max trên cả hai mảng còn lại
  76.     int ans = 0;
  77.     for(int j = 0; j <= A; j++) ans = max(ans, money_dp[j]);
  78.     for(int k = 0; k <= B; k++) ans = max(ans, cone_dp[k]);
  79.     cout << ans << "\n";
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3 10 8
5 5 4
6 7 3
10 6 3
stdout
copy 
21
https://ideone.com/FuxHra
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!