提出 #20535338

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
void solve(){
}
int main(){
    ll n,k;
    cin>>n>>k;
    ll a[n];
    ll dp[n+1][k+1];
    ll prefix[n+1][k+1];
    for(int i=0;i<n;i++)
    cin>>a[i];
    for(int i=0;i<=n;i++)
    for(int j=0;j<=k;j++){   
        dp[0][j]=0; 
        dp[i][0]=1;
        prefix[0][j]=1; 
        prefix[i][0]=1;
    }
    dp[0][0]=1;
    prefix[0][0]=1;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            ll in=max(j-a[i-1],1ll*0),sum;
            
            if(in==0)
            sum=prefix[i-1][j]%mod;
            else sum=(prefix[i-1][j]%mod-prefix[i-1][in-1]%mod+mod)%mod;
            dp[i][j]=sum;
            prefix[i][j]=(prefix[i][j-1]%mod+dp[i][j]%mod)%mod;
            //cout<<i<<" "<<j<<" "<<dp[i][j];
        }
       // cout<<endl;
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=k;j++)
    //     cout<<dp[i][j];
    //     cout<<endl;
    // }
    cout<<dp[n][k];

}

提出情報

ジャッジ結果