Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Apr 15th, 2012  |  syntax: C++  |  size: 0.85 KB  |  hits: 15  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2.  
  3. #include <map>
  4.  
  5. #define MOD 1000000000
  6.  
  7. using namespace std;
  8.  
  9. int mass[40], pw[(1<<19)+1], totmass[1<<20];
  10.  
  11. map<int,int> cnt;
  12.  
  13. int main() {
  14.  
  15.   int N,M,ans = 0;
  16.  
  17.   scanf("%d%d",&N,&M);
  18.  
  19.   for(int i=0;i<M;++i) scanf("%d",&mass[i]);
  20.  
  21.   for(int i=0;i<20;++i) pw[1<<i] = i;
  22.  
  23.   int M2 = M>>1;
  24.  
  25.   totmass[0] = 0;
  26.  
  27.   cnt[0] = 1;
  28.  
  29.   for(int i=1;i<(1<<M2);++i) {
  30.  
  31.     int lb = i&(-i);
  32.  
  33.     if(totmass[i-lb] >= N) totmass[i] = N+1;
  34.  
  35.     else totmass[i] = totmass[i-lb] + mass[pw[lb]];
  36.  
  37.     cnt[totmass[i]]++;
  38.  
  39.   }
  40.  
  41.   for(int i=0;i<(1<<(M-M2));++i) {
  42.  
  43.     if(i) {
  44.  
  45.       int lb = i&(-i);
  46.  
  47.       if(totmass[i-lb] >= N) totmass[i] = N+1;
  48.  
  49.       else totmass[i] = totmass[i-lb] + mass[M2+pw[lb]];
  50.  
  51.     }
  52.  
  53.     ans += cnt[N-totmass[i]];
  54.  
  55.     if(ans >= MOD) ans -= MOD;
  56.  
  57.   }
  58.  
  59.   printf("%d\n",ans);
  60.  
  61. }
create a new version of this paste RAW Paste Data