Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- //https://pastebin.com/uSuh7zuG
- public class DPM_1 {
- //memo[i][j] i children and j candies store the numbers of ways
- //memo[i][0] 1
- //memo[i][j] = memo[i-1][j]+memo[i-1][j-1]+memo[i-1][j-2]+...+memo[i-1][j-ai];
- public static long memo[][] = new long[2][1000005];
- public static long prefixSum[][] = new long[2][1000005];
- public static int a[] = new int[100005];
- public static final long MOD = 1000000007;
- public static void main(String[] args) throws IOException
- {
- BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
- String[] tmp = in.readLine().split(" ");
- int N = Integer.parseInt(tmp[0]);
- int K = Integer.parseInt(tmp[1]);
- tmp = in.readLine().split(" ");
- for (int i = 1; i <= N; i++)
- a[i] = Integer.parseInt(tmp[i-1]);
- memo[0][0] = 1;
- int cur = 1, prev = 0;
- for (int i = 1; i <= N; i++)
- {
- for (int j = 0; j <= K; j++)
- {
- //Using prefixSum to calculate current value
- memo[cur][j] = memo[prev][j];
- if (j-a[i] > 0)
- memo[cur][j] = memo[prev][j]-memo[prev][j-a[i]-1];
- memo[cur][j] %= MOD;
- memo[cur][j] += MOD;
- memo[cur][j] %= MOD;
- }
- //recalculate prefix sum
- for (int j = 1; j <= K; j++)
- memo[cur][j] = (memo[cur][j] + memo[cur][j-1]) % MOD;
- cur ^= 1;
- prev ^= 1;
- }
- System.out.println(memo[prev][K]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement