与えられる \(2\) 数列 \(A\),\(B\) を、\(A_i\) の昇順にまとめてソートします（\(A_i\) の値が同じときは \(B_i\) の大小で区別するなどして適当に順序付けをします）。すると、\(\{1,2,\ldots,N\}\) の空でないすべての部分集合 \(S\) について \(\max_{i \in S} A_i=A_{\max(S)}\) が成り立つことから、問題を以下のように変形させることができます。

\(f(i,j)\) を \((B_1,B_2,\ldots,B_i\) から \(0\) 個以上の要素を選んでそれらの和を \(j\) にする通り数\()\) と定めるとき、以下の値を求めよ。

• \(\sum_{i=1}^{N} \sum_{j=0}^{A_i-B_i} f(i-1,j)\)

明らかに、\(f(i,j)\) に関して、\(i\) の値域は \(0\) 以上 \(N\) 以下であり、また \(j\) の値域は \(0\) 以上 \(\max(A)\) 以下のみしか考えなくてよいです。よって適切に動的計画法を用いて \(f(i,j)\) の値を求めることで、\(O(N \max(A))\) でこの問題を解くことが可能です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

const int mod = 998244353, maxi = 5000;

int main(){
	int N; cin >> N;
	vector<pair<int,int>> data(N);
	for(int i=0; i<N; i++) cin >> data[i].first;
	for(int i=0; i<N; i++) cin >> data[i].second;
	sort(data.begin(),data.end());
	vector<int> A(N),B(N);
	for(int i=0; i<N; i++) tie(A[i],B[i]) = data[i];
	vector<vector<int>> dp(N+1,vector<int>(maxi+1));
	dp[0][0] = 1;
	int ans = 0;
	for(int i=0; i<N; i++){
		for(int j=0; j<=maxi; j++){
			dp[i+1][j] = dp[i][j];
			if(B[i] <= j){
				dp[i+1][j] += dp[i][j-B[i]];
				dp[i+1][j] %= mod;
			}
			if(j <= A[i]-B[i]){
				ans += dp[i][j];
				ans %= mod;
			}
		}
	}
	cout << ans << endl;
}