[Spoj] ADACOINS - Ada and Coins

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : ADACOINS - Ada and Coins
Source            : Spoj
Category          : Bitset
Algorithm         : Bitset
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e5 + 5;  
  
int n, q, arr[maxn];  
bitset <maxn> bs;  
int cumsum[maxn];  
  
inline void calcSubSet()  
{  
      bs.set(0);  
      for (int i = 1; i <= n; i++) bs |= (bs << arr[i]);  
      cumsum[0] = 1;  
      for (int i = 1; i < maxn; i++) cumsum[i] = cumsum[i-1] + (bs.test(i) == true);  
}  
  
int main()  
{  
      scanf("%d %d", &n, &q);  
      for (int i = 1; i <= n; i++) scanf("%d", arr+i);  
      calcSubSet();  
      while (q--)  
      {  
            int l, r;  
            scanf("%d %d", &l, &r);  
            int sum = cumsum[r] - cumsum[l-1];  
            printf("%d\n", sum);  
      }  
}