Advertisement
MinhNGUYEN2k4

Average

Aug 25th, 2021
1,010
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 205
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26. const int Mod = 1000000007;
  27.  
  28. int n, a[N], x;
  29. int t;
  30.  
  31. void readfile()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(0);cout.tie(0);
  35.     if (fopen(Task".inp","r"))
  36.     {
  37.         freopen(Task".inp","r",stdin);
  38.         //freopen(Task".out","w",stdout);
  39.     }
  40.     cin >> t;
  41. }
  42.  
  43. int dp[N][N*N];
  44.  
  45. int calc(int val){
  46.     vector<int> b(a+1,a+1+n);
  47.     for(int i=0; i<n; i++) b[i] -= val;
  48.     int up=0;
  49.     int low = 0;
  50.     int down = 0;
  51.     for(int i=0; i<n; i++) if (b[i] <= 0) down += abs(b[i]);
  52.     for(int i=0; i<n; i++){
  53.         //cout << b[i] << " \n"[i==n-1];
  54.         if (b[i] > 0) up += b[i];
  55.         if (b[i] <= 0) low += b[i];
  56.     }
  57.     memset(dp, 0, sizeof dp);
  58.     dp[0][down]=1;
  59.     for(int i=1; i<=n; i++){
  60.         for(int j=low; j<=up; j++){
  61.             dp[i][j+down] = dp[i-1][j+down];
  62.             if ((j - b[i-1]) + down >= 0){
  63.                 dp[i][j+down] += dp[i-1][j-b[i-1]+down];
  64.                 dp[i][j+down] %= Mod;
  65.             }
  66.         }
  67.     }
  68.     return dp[n][down]-1;
  69. }
  70.  
  71. void solve(){
  72.     cin >> n >> x;
  73.     int sum = 0;
  74.     for(int i=1; i<=n; i++){
  75.         cin >> a[i];
  76.     }
  77.     cout << calc(x) << '\n';
  78. }
  79.  
  80. void proc()
  81. {
  82.     while (t--) solve();
  83. }
  84.  
  85. signed main()
  86. {
  87.     readfile();
  88.     proc();
  89.     return 0;
  90. }
  91.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement