fork download
copy 
  1. /*
  2. ********** Enigm@tic :*: T.L.G.Hiếu @nd HieuT.L.G_aming **********
  3. ***         Viet N@m - Th@nh Ho@ - L@m Son High school         ***
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define hh return;
  8. #define hieupcc int main()
  9. #define t_l_g_h return 0;
  10. #define pb push_back
  11. #define po pop_back
  12. #define ll long long
  13. #define se second
  14. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  15. #define pll pair<ll,ll>
  16. #define pi pair<int,int>
  17. #define v vector<ll>
  18. #define g_h_p_c break;
  19. #define hh return;
  20. #define NMAX 101
  21. //*************************************************************//
  22. int n,k,a[NMAX],m,of=2*1e5 ;
  23. const int mod = 1e9 + 7 ;
  24. const int MAXXXXXXXX = 3*1e5 ;
  25. int dp[2][MAXXXXXXXX + 3],t;
  26. int main()
  27. {
  28.     freopen("PG18R3.INP","r",stdin);
  29.     freopen("PG18R3.OUT","w",stdout);
  30.     fast 
  31.     cin>>t;
  32.     while(t--){
  33.       int s=0;
  34.       cin>>n>>m;
  35.       memset(dp,0,sizeof(dp));
  36.       for(int i=1;i<=n;i++){
  37.         cin>>a[i];
  38.         s+=abs(a[i]);
  39.       }
  40.       if(s<abs(m)){
  41.         cout<<0<<'\n';
  42.         continue;
  43.       }
  44.       dp[0&1][of]=1;
  45.       for(int i=1;i<=n;i++){
  46.       	fill ( dp[i&1] , dp[i&1] +MAXXXXXXXX + 1 , 0 );
  47.          for(int j=-s;j<=s;j++){ 
  48.             dp[i&1][j+of]=(dp[(i-1)&1][j-a[i]+of]%mod+dp[(i-1)&1][j+a[i]+of]%mod)%mod;
  49.          }
  50.       }
  51.       cout<<dp[n&1][m+of]<<'\n';
  52.     }
  53.     return 0;
  54. }
  55. // số cách tạo ra tổng of khi đến vị trí i
  56. // 0 1 3
  57. // 0 + 1 - 3
  58. // - 0 + 1 -3
  59. // -1 + 2 = 1
  60. // -2 + 1 = -1
  61. // 6 + 7 + 3 = 16
  62. // -10 + -9 + -13 =
  63.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j0ZXMt
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!