A dp question in which we first compute the no of subsets of two arrays having a sum s. s ranges from 0 to 200*2000 from the constraints.we will will make two arrays x and y for storing the no of different subsets possible whose sum=i.We will do this using dp approach.Then we will take x[i] one by one and find summation of y[j] where
max( 0,x[i]-q ) <= j <= min(k-1,x[i]+q)
(this can be done in O(n) using prefix sums) and add summ*x[i] to ans.
Remember to take mod at every time you add (add 10^9+7 when you subtract and then take mod) as total subsets could go upto 2^200.
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v) \
cout << endl; \
rep(i, 0, v.size()) cout << v[i] << " "; \
cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))
#define k 400002
ll x[k],y[k];
ll mod(ll n){
return n%(ll)mo;
}
ll gi(ll n){
if(n-1>=0)return y[n-1];
else return 0;
}
int main()
{
fastio
ll n;cin>>n;
ll a[n],b[n];
rep(i,0,n)cin>>a[i];
rep(i,0,n)cin>>b[i];
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
x[0]=1;y[0]=1;
rep(i,0,n){
ll d[k]; fill(d,0); d[0]=1;
rep(j,0,k){
if( x[j]>0)d[j+a[i]]=mod( d[j+a[i]] + x[j]);
}
rep(j,1,k)x[j]=mod(x[j]+d[j]);
}
rep(i,0,n){
ll d[k]; fill(d,0); d[0]=1;
rep(j,0,k){
if( y[j]>0)d[j+b[i]]=mod( d[j+b[i]] + y[j]);
}
rep(j,1,k)y[j]=mod(y[j]+d[j]);
}
ll q;cin>>q;
rep(i,1,k)y[i]=mod(y[i]+y[i-1]);
ll ans=0;
rep(i,0,k){
if(x[i]>0){
ans=mod(ans +mod( x[i]*( mo + y[ (ll)min((ll)k-1,i+q ) ]- gi(i-q) ) ) );
}
}
cout<<ans;
}
achieveit 