fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define clr(a, h) memset(a, (h), sizeof(a))
  5.  
  6. //1 <= n <= 1000 cantidad de productos
  7. //1 <= ai <= 1000 precio de cada producto
  8. //1 <= k <= 10^3 dinero
  9.  
  10. int n, k;
  11. int a[1000 + 10];
  12. int dp[1000 + 10][1000 + 10];
  13.  
  14. ll f(int pos, int gastado) { //(0<=pos<n) (0<=gastado<=k) 
  15.     if(gastado > k) return 0;
  16.     if(pos == n) return gastado; //si ya acabe los productos, retorno lo gastado
  17.  
  18.     if(dp[pos][gastado] == -1) {
  19.         int tomar = f(pos + 1, gastado + a[pos]);
  20.         int no_tomar = f(pos + 1, gastado);
  21.         dp[pos][gastado] =  max(tomar, no_tomar);
  22.     }
  23.  
  24.     return dp[pos][gastado];
  25. }
  26.  
  27. int main() {
  28.     clr(dp, -1);
  29. 	cin >> n >> k;
  30. 	for(int i = 0; i < n; i++)
  31. 	    cin >> a[i];
  32. 	cout << f(0, 0) << "\n";
  33.     return 0;
  34. }
  35.  
Success #stdin #stdout 0.01s 7584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/1ee0ug
language:
C++ (gcc 8.3)
created:
3 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!