Submission #1672688

---

Source Code Expand

#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;
const LL MOD = 1000000007LL;
using namespace std;
int a[2000];
LL dp1[2001][2001];
LL dp2[2001][2001];
int main() {
	int N, M, Q;
	cin >> N >> M >> Q;
	rep(i, N) {
		cin >> a[i];
	}
	rep(i, N + 1) {
		dp1[i][0] = 1;
	}
	rep(i, N) {
		for (int j = 1; j <= M; j++) {
			dp1[i + 1][j] = (dp1[i + 1][j - 1] + dp1[i][j]) % MOD;
			if (j - a[i] - 1 >= 0) dp1[i + 1][j] = (dp1[i + 1][j] - dp1[i][j - 1 - a[i]] + MOD) % MOD;
		}
	}
	rep(i, N) {
		for (int j = 0; j <= M; j++) {
			dp2[i][j] = dp1[N][j];
			if (j > 0) dp2[i][j] = (dp2[i][j] - dp1[N][j - 1] + MOD) % MOD;
			if (j - 1 - a[i] >= 0) (dp2[i][j] += dp2[i][j - 1 - a[i]]) %= MOD;
		}
	}
	rep(i, Q) {
		int k, x;
		cin >> k >> x;
		k--;
		cout << dp2[k][M - x] << endl;
	}
}

Submission Info

Judge Result