fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int N, A, B;
  9.     cin >> N >> A >> B;
  10.     struct Friend { int P, C, X; };
  11.     vector<Friend> f(N);
  12.     for(int i = 0; i < N; i++){
  13.         // đọc vào P_i, C_i, X_i
  14.         cin >> f[i].P >> f[i].C >> f[i].X;
  15.     }
  16.  
  17.     // sort theo X_i tăng để lúc nào cũng \"xài cones\" hiệu quả nhất trước
  18.     sort(f.begin(), f.end(), [&](auto &a, auto &b){
  19.         return a.X < b.X;
  20.     });
  21.  
  22.     const int INF_NEG = -1e9;
  23.     // dp[j][k] = max popularity khi còn j moonie và k cones
  24.     vector<vector<int>> dp(A+1, vector<int>(B+1, INF_NEG));
  25.     vector<vector<int>> nxt(A+1, vector<int>(B+1, INF_NEG));
  26.  
  27.     // khởi: chưa mời ai, có A moonie và B cones, độ phổ biến = 0
  28.     dp[A][B] = 0;
  29.  
  30.     for(int i = 0; i < N; i++){
  31.         auto &P = f[i].P;
  32.         auto &C = f[i].C;
  33.         auto &X = f[i].X;
  34.  
  35.         // reset nxt về -inf
  36.         for(int j = 0; j <= A; j++)
  37.             fill(nxt[j].begin(), nxt[j].end(), INF_NEG);
  38.  
  39.         for(int j = 0; j <= A; j++){
  40.             for(int k = 0; k <= B; k++){
  41.                 int cur = dp[j][k];
  42.                 if(cur < 0) continue;
  43.  
  44.                 // 1) không mời bạn i
  45.                 nxt[j][k] = max(nxt[j][k], cur);
  46.  
  47.                 // 2) mời bạn i
  48.                 //    maxDiscount = min(C, k / X)  (số moonie được giảm tối đa)
  49.                 int maxDiscount = min(C, k / X);
  50.                 int conesUsed   = maxDiscount * X;
  51.                 int moneyCost   = C - maxDiscount;
  52.  
  53.                 // nếu đủ tiền và đủ cones
  54.                 if(j >= moneyCost && k >= conesUsed){
  55.                     int nj = j - moneyCost;
  56.                     int nk = k - conesUsed;
  57.                     nxt[nj][nk] = max(nxt[nj][nk], cur + P);
  58.                 }
  59.             }
  60.         }
  61.         dp.swap(nxt);
  62.     }
  63.  
  64.     // tìm kết quả tốt nhất trên mọi j,k còn lại
  65.     int ans = 0;
  66.     for(int j = 0; j <= A; j++)
  67.         for(int k = 0; k <= B; k++)
  68.             ans = max(ans, dp[j][k]);
  69.  
  70.     cout << ans << "\n";
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3 10 8
5 5 4
6 7 3
10 6 3
stdout
copy 
15
https://ideone.com/vCxWR2
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!