Submission #55023067

---

Source Code Expand

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define sz(a) ((long long)(a).size())
#define X first
#define Y second
 
using ll = long long;
using ull = unsigned long long;
using dbl = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll myRandMod) {
    return (ull)rng() % myRandMod;
}
 
const ll INF = 1e9;
const ll LINF = 1e18;
const int MOD = (int)1e9 + 7;
const int MAXN = 105;
const int MAXVAL = 10;
const int MAXS = MAXN * MAXVAL;

int d[MAXN][2 * MAXS];
bool used[2 * MAXVAL + 5];

void add(int& x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n); 
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    memset(d, 0, sizeof d);
    d[0][MAXS] = 1;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        for (int s = 0; s < 2 * MAXS; ++s) {
            // if (0 <= s - MAXS && s - MAXS <= 2) {
            //     cout << i << " " << s - MAXS << " " << d[i][s] << endl;
            // }
            if (d[i][s] == 0) {
                continue;
            }
            if (s == MAXS) {
                memset(used, 0, sizeof used);
                used[MAXVAL] = 1;
                for (int j = i; j < n; ++j) {
                    if (used[MAXVAL + a[j]]) {
                        continue;
                    }
                    used[MAXVAL + a[j]] = 1;
                    add(d[j + 1][MAXS + a[j]], d[i][s]);
                }

                continue;
            }
            add(d[i + 1][s], d[i][s]);
            // if (s != MAXS) {
                add(ans, d[i][s]);
            // }
            // if (a[i] != 0) {
                add(d[i + 1][s + a[i]], d[i][s]);
            // }
        }
    }
    cout << ans << '\n';
}
 
signed main() {
#ifdef LOCAL
    assert(freopen("in.txt", "r", stdin));
    assert(freopen("out.txt", "w", stdout));
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
 
    int T = 1;
    // cin >> T;
    for (int numt = 0; numt < T; ++numt) {
        solve();
    }
 
#ifdef LOCAL
    cout << endl << endl << "time = " << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
}

Submission Info

Judge Result