Saleh127

UVA 10036 / DP

Oct 22nd, 2021
732
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-22-18.48.36
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10.  
  11. int main()
  12. {
  13.    ios_base::sync_with_stdio(0);
  14.    cin.tie(0);cout.tie(0);
  15.  
  16.    test
  17.    {
  18.         ll n,m,i,j,k,l;
  19.  
  20.         cin>>n>>m;
  21.  
  22.        ll a[n+4];
  23.  
  24.        ll dp[n+4][m+4];
  25.  
  26.        for(i=0;i<n;i++)
  27.        {
  28.             cin>>a[i];
  29.             a[i]+=m;
  30.             a[i]%=m;
  31.        }
  32.  
  33.        memset(dp,0,sizeof dp);
  34.  
  35.        dp[0][0]=1;
  36.  
  37.        for(i=0;i<n;i++)
  38.        {
  39.             for(j=0;j<m;j++)
  40.             {
  41.                  if(dp[i][j])
  42.                  {
  43.                       dp[i+1][(j+a[i]+m)%m]=1;
  44.                       dp[i+1][(j-a[i]+m)%m]=1;
  45.                  }
  46.             }
  47.        }
  48.  
  49.        if(dp[n][0]) cout<<"Divisible"<<endl;
  50.        else cout<<"Not divisible"<<endl;
  51.  
  52.    }
  53.  
  54.  
  55.  
  56.    get_lost_idiot;
  57. }
  58.  
  59.  
  60. /*
  61.  
  62. #include <bits/stdc++.h>
  63. using namespace std;
  64. #define ll long long
  65. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  66. #define get_lost_idiot return 0
  67.  
  68. ll dp[10005][102];
  69. ll a[20005];
  70. ll n,k,ans=0;
  71.  
  72. void solve(ll i, ll sum)
  73. {
  74.      if(i==n+1)
  75.      {
  76.           if(sum%k==0) ans=1;
  77.           return;
  78.      }
  79.  
  80.      ll rem=sum+k;
  81.  
  82.      rem%=k;
  83.  
  84.      if(dp[i][rem]!=-1) return ;
  85.  
  86.      dp[i][rem]=1;
  87.  
  88.      rem=sum+a[i];
  89.  
  90.      solve(i+1,rem);
  91.  
  92.      rem=sum-a[i];
  93.  
  94.      solve(i+1,rem);
  95.  
  96. }
  97.  
  98. int main()
  99. {
  100.    ios_base::sync_with_stdio(0);
  101.    cin.tie(0);cout.tie(0);
  102.  
  103.  
  104.    test
  105.    {
  106.         ll i,j;
  107.  
  108.         cin>>n>>k;
  109.  
  110.         for(i=1;i<=n;i++) cin>>a[i];
  111.  
  112.         memset(dp,-1,sizeof dp);
  113.  
  114.         ans=0;
  115.  
  116.         solve(0,0);
  117.  
  118.         if(ans) cout<<"Divisible"<<endl;
  119.         else cout<<"Not divisible"<<endl;
  120.    }
  121.  
  122.  
  123.    get_lost_idiot;
  124. }
  125. */
  126.  
RAW Paste Data