Advertisement
Guest User

Untitled

a guest
Mar 1st, 2021
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const int N = 2e3+5;
  7. const int K = 2e3+5;
  8. const int MOD = 1879048192;
  9.  
  10.  
  11. int n, k, credits[N];
  12.  
  13. ll dp[N][K];
  14.  
  15. ll solve(int i, int sum) {
  16.     if(sum > k)
  17.         return 0;
  18.     if(i == n)
  19.         return 1;
  20.     if(dp[i][sum] != -1)
  21.         return dp[i][sum];
  22.     return dp[i][sum] = (solve(i + 1, sum) + solve(i + 1, sum + credits[i])) % MOD;
  23. }
  24.  
  25. int main()
  26. {
  27.     cin >> n >> k;
  28.     for(int i = 0; i < n; i++)
  29.         cin >> credits[i];
  30.     memset(dp, -1, sizeof(dp));
  31.     ll ret = 0;
  32.     for(int i = 0; i < n; i++)
  33.         ret = (ret + solve(i + 1, credits[i])) % MOD;
  34.     cout << ret + 1 << " " << (ret + 1) % MOD << "\n";
  35.     if ((ret + 1) != (ret + 1) % MOD)
  36.         cout << "CORRECT\n";
  37.     else
  38.         cout << "INCORRECT\n";
  39.     return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement