fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int cache[10000][1000];
  4. int dp(int A, vector<int> &B,int i)
  5. {
  6.     if(A==0)
  7.         return 0;
  8.  
  9.     if(i==B.size())
  10.     {
  11.         if(A>=0)
  12.             return 0;
  13.         return INT_MIN;
  14.     }
  15.     if(cache[A][i]!=-1)
  16.     {
  17.         return cache[A][i];
  18.     }
  19.     int ans=dp(A,B,i+1);
  20.     if(B[i]>A)
  21.     {
  22.         ans=max(ans,0);
  23.     }
  24.     else
  25.         ans=max(ans,dp(A-B[i],B,i)+1);
  26.     cache[A][i]=ans;
  27.     return ans;
  28. }
  29. void print(int A, vector<int> &B,int i, vector<int> &ans)
  30. {
  31.     if(i==B.size()) return;
  32.  
  33.     if(B[i]<=A && (dp(A-B[i],B,i)+1)==cache[A][i])
  34.     {
  35.         ans.push_back(i);
  36.         print(A-B[i],B,i,ans);
  37.     }
  38.     else
  39.     {
  40.         print(A,B,i+1,ans);
  41.     }
  42. }
  43.  
  44. vector<int> solve(int A, vector<int> &B) {
  45.     memset(cache,-1,sizeof(cache));
  46.     vector<int> ans;
  47.     dp(A,B,0);
  48.     print(A,B,0,ans);
  49.     return ans;
  50. }
  51.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/x86_64-linux-gnu/6/../../../x86_64-linux-gnu/Scrt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/WrYMyK
language:
C++14 (gcc 8.3)
created:
4 years 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!