fork download
copy 
  1. #include<bits/stdc++.h>
  2. //#include <boost/multiprecision/cpp_int.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. #define fast std::ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  8. #define clr0(a) memset((a), 0, sizeof(a))
  9. #define clr1(a) memset((a), -1, sizeof(a))
  10. #define srtin1 cin.ignore ( std::numeric_limits<std::streamsize>::max(), '\n' );
  11. #define strin2 getline(cin, text);
  12. #define ll long long
  13. #define test cout<<"archit\n"
  14. #define debug(x) cout<<x<<" "
  15. #define debug1(x) cout<<x<<"\n"
  16. #define debug2(x,y) cout<<x<<" "<<y<<"\n"
  17. #define debug3(x, y, z) cout<<x<<" "<<y<<" "<<z<<"\n"
  18. #define pb push_back
  19. #define pi pair<int,int>
  20. #define fi first
  21. #define si second
  22. #define mod (ll)1000000007
  23. #define mxn 1000005
  24. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  25. using namespace std;
  26. //using namespace boost::multiprecision;
  27. using namespace __gnu_pbds;
  28. typedef struct node
  29. {
  30.     int val,wt;
  31. }node;
  32. int dp[1005][1005];
  33. int solve(node* arr, int n, int weight)
  34. {
  35.     memset(dp, 0, sizeof(dp));
  36.     for(int i=0;i<=weight;i++){
  37.         dp[0][i] = INT_MAX;
  38.     }
  39.     for(int i=0;i<=n;i++){
  40.         dp[i][0] = 0;
  41.     }
  42.     for(int i=1;i<=n;i++){
  43.         for(int j=1;j<=weight;j++){
  44.             dp[i][j] = dp[i-1][j];
  45.             if(arr[i-1].val == -1){
  46.                 continue;
  47.             }
  48.             if(arr[i-1].wt<=j){
  49.                 if(dp[i][j - arr[i-1].wt]!=INT_MAX)
  50.                     dp[i][j] = min(dp[i][j], arr[i-1].val + dp[i][j - arr[i-1].wt]);
  51.             }
  52.         }
  53.     }
  54.     return dp[n][weight];
  55. }
  56. int main()
  57. {
  58.     fast;
  59.     int n,w;
  60.     cin>>n>>w;
  61.     node* arr = new node[n];
  62.     for(int i=1;i<=n;i++){
  63.         int p; cin>>p;
  64.         arr[i-1].wt = i;
  65.         arr[i-1].val = p;
  66.     }
  67.     int ans = solve(arr, n, w);
  68.     if(ans == INT_MAX){
  69.         ans = -1;
  70.     }
  71.     debug(ans);
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 19184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/V5RmvC
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!