Untitled

 avatar
user_2740508
plain_text
2 years ago
853 B
3
Indexable
Never
#include<bits/stdc++.h>
#define lli long long int
#define mod 1000000007

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    vector<int> dp(3010, 0);
    for (int i = 0; i <= v[0]; i++) {
        dp[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        vector<int> dp1(3010, 0);
        for (int i = 1; i < 3010; i++) {
            dp[i] = (dp[i - 1] + dp[i]) % mod;
        }
        for (int j = 0; j <= v[i]; j++) {
            int mv = v[i - 1] - v[i] + j;
            mv = min(mv, j);
            if (mv >= 0) {
                dp1[j] = dp[mv];
            }
        }
        dp = dp1;
    }
    int ans = 0;
    for (int i = 0; i < 3010; i++) {
        ans = (ans + dp[i]) % mod;
    }
    cout << ans << '\n';
}