Submission #55037951

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint1000000007;

int main(){
    // input
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;
    
    // init
    const int L = 1010; // non - negative
    const int R = 12;
    vector<mint> dp1(L * 2), dp2(R * 2);
    dp1[L] = 1;
    
    // calc
    for (int i = 0; i < N; i++){
        // not in A[i]
        auto n_dp1 = dp1;
        for (int j = 0; j < L * 2; j++){
            if (j == L || dp1[j] == 0) continue;
            // in A[i]
            n_dp1[j + A[i]] += dp1[j];
        }
        // j = 0
        if (A[i]){
            n_dp1[L + A[i]] += dp1[L] - dp2[A[i] + R];
            dp2[A[i] + R] = dp1[L];
        }
        // dp1[i] <- dp1[i + 1]
        swap(dp1, n_dp1);
    }
    
    // output
    mint ans = 0;
    for (auto x : dp1) ans += x;
    for (auto x : dp2) ans -= x;
    cout << ans.val() << "\n";
}

Submission Info

Judge Result