fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. ll mod=1e9+7;
  5. const int N=1e5+2;
  6. ll dp[N][102];
  7. ll a[106];
  8. ll solve(ll i,ll n,ll k)
  9. {
  10.   if(k==0)
  11.     return 1;
  12.   if(i>n)
  13.     return 0;
  14.   if(dp[k][i]!=-1)
  15.     return dp[k][i];
  16.   ll ans=0;
  17.   for(int j=0;j<=a[i];j++)
  18.     if(k>=j)
  19.     ans=(ans+solve(i+1,n,k-j))%mod;
  20.     return dp[k][i]=ans;
  21. }
  22. int main()
  23. {
  24.   int n,k;
  25.   cin>>n>>k;
  26.   memset(dp,-1,sizeof(dp));
  27.   for(int i=1;i<=n;i++)
  28.     cin>>a[i];
  29.     cout<<solve(1,n,k);
  30. }
Time limit exceeded #stdin #stdout 5s 82856KB
comments (?)
stdin
copy 
4 100000
100000 100000 100000 100000
stdout
copy 
Standard output is empty
https://ideone.com/1wV9fq
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!