fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Friend {
  5.     int p, c, x;
  6. };
  7.  
  8. int main() {
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     int N, A, B;
  13.     cin >> N >> A >> B;
  14.     vector<Friend> f(N);
  15.     for (int i = 0; i < N; i++) {
  16.         cin >> f[i].p >> f[i].c >> f[i].x;
  17.     }
  18.     // Sort by X ascending to apply cones greedily
  19.     sort(f.begin(), f.end(), [](const Friend &a, const Friend &b) {
  20.         return a.x < b.x;
  21.     });
  22.  
  23.     // dp layers: 0 = previous i, 1 = current i
  24.     const int INF_NEG = -1e9;
  25.     vector<vector<int>> dp_prev(A+1, vector<int>(B+1, 0));
  26.     vector<vector<int>> dp_cur(A+1, vector<int>(B+1, 0));
  27.  
  28.     dp_prev[A][B] = 0; // start with full A mooney and B cones, 0 popularity
  29.  
  30.     for (int i = 0; i < N; i++) {
  31.         // Reset current layer
  32.         for (int j = 0; j <= A; j++) {
  33.             fill(dp_cur[j].begin(), dp_cur[j].end(), 0);
  34.         }
  35.  
  36.         for (int j = 0; j <= A; j++) {
  37.             for (int k = 0; k <= B; k++) {
  38.                 int val = dp_prev[j][k];
  39.                 if (val < 0) continue;
  40.                 // 1) Do not invite friend i
  41.                 dp_cur[j][k] = max(dp_cur[j][k], val);
  42.  
  43.                 // 2) Invite friend i
  44.                 int Ci = f[i].c;
  45.                 int Xi = f[i].x;
  46.                 int Pi = f[i].p;
  47.                 // spend as many cones as possible on this friend
  48.                 int use_cones = min(k, Ci * Xi);
  49.                 int discount = use_cones / Xi;
  50.                 int pay = Ci - discount;
  51.                 if (j >= pay) {
  52.                     int nj = j - pay;
  53.                     int nk = k - use_cones;
  54.                     dp_cur[nj][nk] = max(dp_cur[nj][nk], val + Pi);
  55.                 }
  56.             }
  57.         }
  58.         // swap layers
  59.         dp_prev.swap(dp_cur);
  60.     }
  61.  
  62.     // Answer = max popularity over all remaining budgets
  63.     int ans = 0;
  64.     for (int j = 0; j <= A; j++) {
  65.         for (int k = 0; k <= B; k++) {
  66.             ans = max(ans, dp_prev[j][k]);
  67.         }
  68.     }
  69.     cout << ans;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
3 10 8
5 5 4
6 7 3
10 6 3
stdout 
15
https://ideone.com/q3N6k7
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!