pastebin

Paste Search Dynamic
Recent pastes
dp
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.         // your code goes here
  6.         int n;
  7.         cin>>n;
  8.         int a[n];
  9.         for(int i=0;i<n;i++)
  10.          cin>>a[i];
  11.         int M=1<<20;
  12.         int dp[M];
  13.         char res[M];
  14.         for(int i=1;i<M;i++)
  15.          dp[i]=int_max;
  16.         for(int i=0;i<n;i++)
  17.         {
  18.                 if(a[i]==0)
  19.                  continue;
  20.                 for(int j=0;j<M;j++)
  21.                  res[j]=0;
  22.                 for(int k=0;k<M;k++)
  23.                  {
  24.                         if(res[k]==1)
  25.                          continue;
  26.                         if(dp[k]>dp[k^a[i]])
  27.                          dp[k]=dp[k^a[i]]+1;
  28.                         else if(dp[k^a[i]]>dp[k])
  29.                          dp[k^a[i]]=dp[k]+1;
  30.                         res[k^a[i]]=1;
  31.                         
  32.                  }
  33.                  
  34.         }
  35.         int j=M-1,k=n>>1;
  36.         while(dp[j]>k)
  37.          j--;
  38.         cout<<j;
  39.         return 0;
  40. }
Parsed in 0.004 seconds