Submission #68598478

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
template<typename T, typename T2>
inline void chmin(T &x, T2 &&y) { x = min(x, y); }
template<typename T, typename T2>
inline void chmax(T &x, T2 &&y) { x = max(x, y); }
typedef long long ll;

const int N = 5005, p = 998244353;
int n, a[N], b[N], l, r;
int sufa[N], preb[N];

int f[N][N], g[N][N];

int calc(int mn)
{
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    
    f[0][0] = sufa[1] >= mn;
    rep(i, 0, n) g[0][i] = 1;

    rep(i, 1, n)
    {
        rep(j, 0, i - 1) if(sufa[i + 1] + preb[j] >= mn)
        {
            f[i][j] = g[i - 1][j];
        }

        g[i][0] = f[i][0];
        rep(j, 1, n) g[i][j] = (g[i][j - 1] + f[i][j]) % p;
    }
    // cerr << mn << " " << g[n][n] << endl;
    return g[n][n];
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> l >> r;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> b[i];
    per(i, n, 1) sufa[i] = sufa[i + 1] + a[i];
    rep(i, 1, n) preb[i] = preb[i - 1] + b[i];
    cout << ((calc(preb[n] - r) - calc(preb[n] - (l - 1))) % p + p) % p;

    return 0;
}

Submission Info

Judge Result