Cod sursa(job #406386)

Utilizator bora_marianBora marian bora_marian Data 1 martie 2010 14:57:05
Problema Aliens Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<fstream>
#include<algorithm>
using namespace std;
void afis();
struct caract{
       int veve;
       int x,y;};
struct nod{
       int info;
       nod *next;};
nod *a[25];
caract v[105];
caract mm[25];
int k,r,m,n;
int sol[25],maxim;
ofstream fout("veve.out");
void back(int i); 
int suma();
int main()
{
    ifstream fin("veve.in");
    fin>>k>>r;
    fin>>m;
    int i,j,q;
    for(i=1;i<=m;i++)
    {
      fin>>mm[i].x;
      fin>>mm[i].y;
    }
    fin>>n;
    for(i=1;i<=n;i++)
     fin>>v[i].x>>v[i].y>>v[i].veve;
    for(i=1;i<=m;i++)
      for(j=1;j<=n;j++)
        if(((mm[i].x-v[j].x)*(mm[i].x-v[j].x)+(mm[i].y-v[j].y)+(mm[i].y-v[j].y))<=r*r)
          {
            nod *p;
            p=new nod;
            p->info=j;
            p->next=a[i];
            a[i]=p;
          }                                                                            
  back(1);
  fout<<maxim;
  return 0;
}
  void back(int i)  
  {  
    int is;
    for(is=sol[i-1]+1;is<=m;is++)
    {
      sol[i]=is;
      if(i==k)
       { 
        //afis();
        if(suma()>maxim)   
           maxim=suma();
        }   
      else
        back(i+1);
      }
}                                                                             
int suma()
{
  int i,apare[105];
  int sum=0;
  for(i=1;i<=n;i++)
    apare[i]=0;
  for(i=1;i<=k;i++)
   { 
    for(nod*p=a[sol[i]];p;p=p->next)
       if(apare[p->info]==0) 
          sum+=v[p->info].veve,apare[p->info]=1;  
    }     
   return sum;
}      
void afis()
{
     int i;
     for(i=1;i<=k;i++)
      fout<<sol[i];
     fout<<endl;
}