提出 #18243135

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define ll long long
#define nl "\n"
#define ii pair<int, int>
#define MOD 1000000007
#define inf 1L << 60
using namespace std;

const int M = 1e5 + 7;
int n, a[101], k;
ll dp[M];

ll add(ll a, ll b){
    return (a + b) % MOD;
}

ll sub(ll a, ll b){
    return(a - b + MOD) % MOD;
}

void solve()
{
    cin >> n >> k;

    for(int i = 0; i < n; i++) cin >> a[i];

    dp[0] = 1;

    for(int i = 0; i < n; i++){

        vector < int > prefix(k + 2, 0);

        for(int j = k; j >= 0; j--){

            ll tmp = dp[j];

            int L = j + 1;
            int R = j + min(a[i], k - j);

            prefix[L] = add(prefix[L], tmp);
            prefix[R + 1] = sub(prefix[R + 1], tmp);
            // for(int here = L; here <= R; here++){

            //     dp[here] = add(dp[here], tmp);
            // }
        
        }

        int csum = 0;

        for(int i = 0; i <= k; i++){

            csum = add(csum, prefix[i]);

            dp[i] = add(dp[i], csum);
        }
    }
    cout << dp[k] << nl;
}


int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);

    int t = 1;
    //cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

提出情報

ジャッジ結果