Advertisement
am1x

Untitled

Aug 17th, 2021
1,018
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <inttypes.h>
  4.  
  5. typedef unsigned int uint_t;
  6. const uint_t N = 1000000, LK = 30, B = 100000000;
  7.  
  8. static uint_t read_uint()
  9. {
  10.     const uint_t D = 10;
  11.     uint_t u = 0;
  12.     do {
  13.         int c = getchar_unlocked();
  14.         assert (0 <= c);
  15.         u = c - '0';
  16.     } while (D <= u);
  17.    
  18.     for (;;) {
  19.         uint_t v = getchar_unlocked() - '0';
  20.         if (D <= v)
  21.             break;
  22.         u = u * D + v;
  23.     }
  24.     return u;
  25. }
  26.  
  27. int main()
  28. {
  29.     uint_t ms[LK];
  30.     uint64_t ss[LK];
  31.    
  32.     uint_t n = read_uint();
  33.     assert (0 < n && n <= N);
  34.     uint_t k = read_uint();
  35.     assert ((k >> LK) == 0);
  36.  
  37.     uint_t m = 0;
  38.     ms[m++] = k;
  39.     {
  40.         uint_t j = 0;
  41.         while (k & (1U << j))
  42.             j++;
  43.         for (; j < LK; j++) {
  44.             uint_t jm = (1U << j);
  45.             if ((k & jm) == 0)
  46.                 continue;
  47.             uint_t k1 = (k & ~(jm)) | (jm - 1);
  48.             //fprintf(stderr, "adding k1=%u\n", k1);
  49.             ms[m++] = k1;
  50.         }
  51.     }
  52.    
  53.     for (uint_t i = 0; i < m; i++)
  54.         ss[i] = 0;
  55.    
  56.     for (uint_t i = 0; i < n; i++) {
  57.         uint_t a = read_uint();
  58.         assert ((a >> LK) == 0);
  59.         uint_t b = read_uint();
  60.         assert (0 < b && b <= B);
  61.         //fprintf(stderr, "checking pair (%u, %u) \n", a, b);
  62.         for (uint_t j = 0; j < m; j++) {
  63.             if ((~ms[j] & a) == 0) {
  64.                 ss[j] += b;
  65.                 //fprintf(stderr, "it passed m=%u\n", ms[j]);
  66.             }
  67.         }
  68.     }
  69.  
  70.     uint64_t res = ss[0];
  71.     for (uint_t i = 1; i < m; i++) {
  72.         if (res < ss[i])
  73.             res = ss[i];
  74.     }
  75.     printf("%" PRIu64 "\n", res);
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement