fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector <int> v[100];
  8. int n,m,x,y;
  9. int ob[100];
  10. int ob1[100];
  11. int a[1000];
  12. int ans,cur;
  13. long long ways;
  14. int c[100];
  15. long long w;
  16.  
  17. void rek(int x,int *ob,int *ob1,int cur,long long  w)
  18. {
  19.  
  20.    if (x==n+1)
  21.    {
  22.        if (cur>ans)
  23.        {
  24.            ans=cur;
  25.            ways=w;
  26.        }
  27.        else
  28.         if (cur==ans) ways+=w;
  29.    } else
  30.     if (ob[x]==1) rek(x+1,ob,ob1,cur,w); else
  31.     {
  32.         int  p=0;
  33.         for (int i=0;i<v[x].size();i++)
  34.          if (v[x][i]>x && !ob[v[x][i]]) p++;
  35.  
  36.          if (!p)
  37.          {
  38.              if (c[x]==0) w*=2;
  39.              ob[x]=1;
  40.              cur+=c[x];
  41.              rek(x+1,ob,ob1,cur,w);
  42.              ob[x]=0;
  43.          } else
  44.    {
  45.           rek(x+1,ob,ob1,cur,w);
  46.             ob[x]=1;
  47.           for (int i=0;i<v[x].size();i++)
  48.             if (v[x][i]>x)
  49.             {
  50.               ob1[v[x][i]]++;
  51.               ob[v[x][i]]=1;
  52.             }
  53.             cur+=c[x];
  54.             rek(x+1,ob,ob1,cur,w);
  55.             ob[x]=0;
  56.             for (int i=0;i<v[x].size();i++)
  57.             if (v[x][i]>x)
  58.             {
  59.                 ob1[v[x][i]]--;
  60.                 if (!ob1[v[x][i]]) ob[v[x][i]]=0;
  61.             }
  62.       }
  63.     }
  64. }
  65. int main()
  66. {
  67.   scanf("%d%d",&n,&m);
  68.  
  69.   for (int i=1;i<=n;i++)
  70.     scanf("%d",&c[i]);
  71.  
  72.   for (int i=0;i<m;i++)
  73.   {
  74.       scanf("%d%d",&x,&y);
  75.        v[y].push_back(x);
  76.        v[x].push_back(y);
  77.   }
  78.  
  79.  int d=0;
  80.  
  81.  for (int i=1;i<=n;i++)
  82.    if (v[i].size()==0 && c[i]==0)
  83.    {
  84.        d++;
  85.        ob[i]=1;
  86.     }
  87.     else
  88.     if (v[i].size()==0) {
  89.     cur+=c[i];
  90.     ob[i]=1;
  91.     }
  92.  
  93.   rek(1,ob,ob1,cur,1);
  94.  
  95.   printf("%d %lld\n",ans,ways*1<<d);
  96.  
  97. return 0;
  98. }
  99.  
  100. //I don't like BLACK MAGIC !!!
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
https://ideone.com/iRublV
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!