Submission #25106727

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
void solve(){
}
int main(){
   int n,K;
   cin>>n>>K;
   ll a[n];
   for(int i=0;i<n;i++)
   cin>>a[i];
 
  // dp[i][j] represents the total number of ways to 
  //distribute j candies among first i ppl;
  ll dp[101][100001];
  memset(dp,0,sizeof(dp));
 for(int i=0;i<100001;i++){
      dp[0][i]=(i<=a[0])?1:0; 
      if(i==0)
      dp[i][0]=1;
      if(i!=0){
          dp[0][i]+=dp[0][i-1];
      }
  }
 
  
  for(int i=1;i<n;i++){
      for(int k=0;k<100001;k++){
          ll first=dp[i-1][k];
          ll second=((k-a[i]-1<0)?0:dp[i-1][k-a[i]-1]);
        //  cout<<i<<" "<<k<<" "<<first<<" "<<second<<" "<<first-second<<endl;
          //cout<<i<<" "<<k<<" "<<dp[i-1][k]<<" "<<((k-a[i]-1<0)?0:dp[i-1][k-a[i]-1])<<" "<<(dp[i-1][k]- (k-a[i]-1<0)?0:dp[i-1][k-a[i]-1])<<endl;
          dp[i][k]=(first-second+2*mod)%mod;
          dp[i][k]+=((k-1<0)?0:dp[i][k-1]);
          dp[i][k]%=mod;
      }
  } 

  
  cout<<(dp[n-1][K]-(K-1>=0?dp[n-1][K-1]:0)+2*mod)%mod;

}

Submission Info

Judge Result