daily pastebin goal
10%
SHARE
TWEET

Some1

a guest Jun 29th, 2015 199 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MAX 5000
  5. #define inf (1<<29)
  6. typedef long long int LL;
  7.  
  8. int sq[MAX+10];
  9. LL dp[MAX+10][MAX+10];
  10. int cor[MAX+10];
  11.  
  12. vector<int> idx[MAX+10], val[MAX+10];
  13.  
  14. int main()
  15. {
  16.     int i, j, k, n, pt, cur,p, t;
  17.  
  18.     scanf("%d", &t);
  19.     while(t--)
  20.     {
  21.         scanf("%d %d", &n, &pt);
  22.         for(i = 1; i <= n; i++)
  23.             scanf("%d", &sq[i]), cor[i] = sq[i] | cor[i-1];
  24.  
  25.         for(j = 1; j <= n; j++, cur = 0)
  26.         {
  27.             for(i = j; i >= 1; i--)
  28.             {
  29.                 cur |= sq[i];
  30.  
  31.                 if(val[j].empty() || val[j].back() != cur)
  32.                 {
  33.                     val[j].push_back(cur);
  34.                     idx[j].push_back(i);
  35.                 }
  36.             }
  37.         }
  38.  
  39.  
  40.         for(k = 1; k <= pt; k++)
  41.             for(p = 0; p <= n; p++)
  42.                 if(p < k) dp[p][k] = -inf;
  43.                 else if(k == 1) dp[p][k] = cor[p];
  44.                 else
  45.                 {
  46.                     dp[p][k] = -inf;
  47.                     for(i = 0 ; i < idx[p].size(); i++)
  48.                     {
  49.                         if(idx[p][i]-1 < k-1) break;
  50.                         dp[p][k] = max(dp[p][k], dp[idx[p][i]-1][k-1] + val[p][i]);
  51.                     }
  52.                 }
  53.  
  54.         printf("%lld\n", dp[n][pt]);
  55.  
  56.         for(i = 1; i<= n; i++)
  57.             val[i].clear(), idx[i].clear();
  58.     }
  59.  
  60.     return 0;
  61. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top