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[X+1][N+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[j][i]=1;
  33.                else{
  34.                   int op1=(i>=1) ? dp[j][i-1]:0;
  35.                   int op2=(j>=c[i])? dp[j-c[i]][i]:0;
  36.                 dp[j][i]=(op1+op2)%mod;
  37.                }
  38.         }
  39.  
  40.     }
  41.       cout<<dp[x][n-1];
  42.  
  43.  
  44. }
  45. int main()
  46. {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(0);
  49.     cout.tie(0);
  50.     int tc = 1;
  51.     //cin >> tc;
  52.     for(int k = 1 ;k <= tc; k++){
  53.        // cout<<"Case #"<<k<<": ";
  54.         solve();
  55.  
  56.     }
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 4196KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/FEJaSC
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!