fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mp make_pair
  5. #define mod 1000000007
  6. #define INF  INT_MAX
  7. #define F first
  8. #define S second
  9. #define ld long double
  10. #define ll long long
  11. #define pii pair<int,int>
  12. #define pll pair<ll,ll>
  13. #define vpii vector<pii>
  14. #define rep(i,n) for(i=0;i<n;i++)
  15. #define repr(i,n) for(i=n-1;i>=0;i--)
  16. #define o4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl;
  17. #define initial(arr,val) memset(arr,val,sizeof(arr))
  18. #define value(x) cout << #x << " is " << x << endl;
  19. const int dx[8] = {-1, 0, 0, 1, 1, 1, -1, -1};
  20. const int dy[8] = { 0, -1, 1, 0, -1, 1, -1, 1};
  21. const int N=101,X=1e6+2;
  22. int dp[N+1][X+1];
  23. int c[N+1];
  24. void solve(){
  25.     int n,x;
  26.     cin>>n>>x;
  27.     for(int i=0;i<n;i++)
  28.         cin>>c[i];
  29.     for(int i=0;i<n;i++){
  30.         for(int j=0;j<=x;j++){
  31.                 if(j==0)
  32.                 dp[i][j]=1;
  33.                else{
  34.                   int op1=(i>=1) ? dp[i-1][j]:0;
  35.                   int op2=(j>=c[i])? dp[i][j-c[i]]:0;
  36.                 dp[i][j]=(op1+op2)%mod;
  37.  
  38.                }
  39.         }
  40.  
  41.     }
  42.       cout<<dp[n-1][x];
  43.  
  44.  
  45. }
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(0);
  50.     cout.tie(0);
  51.     int tc = 1;
  52.     //cin >> tc;
  53.     for(int k = 1 ;k <= tc; k++){
  54.        // cout<<"Case #"<<k<<": ";
  55.         solve();
  56.  
  57.     }
  58.     return 0;
  59. }
  60.  
  61.  
  62.  
  63.  
Runtime error #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pGz2oB
language:
C++ (gcc 8.3)
created:
3 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!