fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <limits.h>
  8. #define s(a) scanf("%d",&a)
  9. #define p(a) printf("%d",a)
  10. using namespace std;
  11.  
  12. struct coordinates
  13. {
  14.     int x,y;
  15. };
  16. struct nodes
  17. {
  18.     int x,y,w;
  19. };
  20.  
  21. coordinates a[22];  // structure array to store co-ordinates of locations
  22. nodes b[102];       // structure array to store co-ordinates of solitaire and number of peoples.
  23. bool visited[102];  // boolean array to mark a check if a particular node is previously visited or not
  24.  
  25. // Utility functionn to count number of set bits... complexity of this is log(n)
  26. int countSetBits(int n)
  27. {
  28.     int count = 0;
  29.     while (n)
  30.     {
  31.       n &= (n-1) ;
  32.       count++;
  33.     }
  34.     return count;
  35. }
  36. /*
  37. what i'm trying to do is taking all subsets of location
  38. and see if this subset has number of set bits equal to number of restaurant i.e. k
  39. if so, iterate over this subset and for each set bit calculate the total number of
  40. people. Update the answer if required. But getting TLE :/
  41. */
  42.  
  43. int k,r,m,i,j,n,p,ans=INT_MIN,subsets,current_sum;
  44. int main()
  45. {
  46.     //freopen("input.txt","r",stdin);
  47.  
  48.     // Inputs dude Inputs :P ==============
  49.     s(k);s(r);
  50.     s(m);
  51.     for(i=0;i<m;i++)
  52.     { s(a[i].x); s(a[i].y); }
  53.     s(n);
  54.     for(i=0;i<n;i++)
  55.     { s(b[i].x); s(b[i].y); s(b[i].w); }
  56.     //=====================================
  57.  
  58.     subsets=(1<<m);
  59.  
  60.     //Iterate through all subsets
  61.     for(i=1;i<subsets;i++)
  62.     {
  63.         //if set bits equal to number of restaurant i.e. k
  64.         if(k==countSetBits(i))
  65.         {
  66.             // mark every solitaire as unvisited
  67.             memset(visited,0,sizeof(visited));
  68.             current_sum=0;
  69.  
  70.             // check for possible sum
  71.             for(j=0;j<m;j++)
  72.             {
  73.                 if((i&(1<<j))>0) // if this is set then find all nodes in range of j'th location
  74.                 {
  75.                     coordinates source=a[j]; // make j as a source
  76.                     for(p=0;p<n;p++) // check on all destination nodes
  77.                     {
  78.                         nodes destinatn=b[p];
  79.  
  80.                         // distance between source and destination
  81.                         double distance=(double)((source.x-destinatn.x)*(source.x-destinatn.x) + (source.y-destinatn.y)*(source.y-destinatn.y));
  82.  
  83.                         // if this node is not visited and range is covered, add its weight and make the node visited
  84.                         if(!visited[p] && distance<=(double)(r*r))
  85.                         {
  86.                             current_sum+=destinatn.w;
  87.                             visited[p]=true;
  88.                         }
  89.                     }
  90.                 }
  91.             }
  92.  
  93.             // if current sum is larger than previous one, update answer
  94.             if(current_sum>ans)
  95.                 ans=current_sum;
  96.         }
  97.     }
  98.     printf("%d",ans);
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
3 3 
5 
0 0 
1 6 
2 3 
6 6 
7 2 
8 
0 1 2 
0 5 3 
0 6 1 
1 0 1 
3 2 3 
3 6 2 
6 2 4 
8 6 3
stdout
copy 
17
https://ideone.com/qPAasG
language:
C++ (gcc 8.3)
created:
9 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!