SHARE
TWEET

Untitled

a guest Nov 9th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Candies {
  5.  
  6.     //memo[i][j]   i children and j candies store the numbers of ways
  7.     //memo[i][0]   1
  8.     //memo[i][j] = memo[i-1][j]+memo[i-1][j-1]+memo[i-1][j-2]+...+memo[i-1][j-ai];
  9.  
  10.     public static long memo[][] = new long[2][1000005];
  11.     public static int a[] = new int[100005];
  12.     public static final long MOD = 1000000007;
  13.  
  14.     public static void main(String[] args) throws IOException
  15.     {
  16.         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  17.         String[] tmp = in.readLine().split(" ");
  18.         int N = Integer.parseInt(tmp[0]);
  19.         int K = Integer.parseInt(tmp[1]);
  20.  
  21.         tmp = in.readLine().split(" ");
  22.         for (int i = 1; i <= N; i++)
  23.             a[i] = Integer.parseInt(tmp[i-1]);
  24.  
  25.         memo[0][0] = 1;
  26.         int cur = 1, prev = 0;
  27.         for (int i = 1; i <= N; i++)
  28.         {
  29.             for (int j = 0; j <= K; j++)
  30.             {
  31.                 memo[cur][j] = memo[prev][j];
  32.                 if (j-a[i] > 0)
  33.                     memo[cur][j] -= memo[prev][j-a[i]-1];
  34.                 memo[cur][j] %= MOD;
  35.                 memo[cur][j] += MOD;
  36.                 memo[cur][j] %= MOD;
  37.             }
  38.             for (int j = 1; j <= K; j++)
  39.                 memo[cur][j] = (memo[cur][j] + memo[cur][j-1]) % MOD;
  40.             cur ^= 1;
  41.             prev ^= 1;
  42.         }
  43.         System.out.println(memo[prev][K]);
  44.     }
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top