# APIO2007[动物园/zoo]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-19

DESCRIPTION:

\$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

#include <time.h>

#define SIGHT 5

#define MAXC 50000

#define MAXN 10000

#define MAXK 2

#define K(k) ((k)%MAXK)

#define MAX(a,b) ((a)>(b)?(a):(b))

#define print(state,string)\

printf(“%s%d%d%d%d%d”,\

string,\

(((state)&(1<<4))>>4),\

(((state)&(1<<3))>>3),\

(((state)&(1<<2))>>2),\

(((state)&(1<<1))>>1),\

(((state)&(1<<0))>>0));

typedef unsigned bit;

struct Child{int pos;bit love,hate;};

int N,C;

Child children[MAXC];

int f[MAXK][1<<(SIGHT)];

int main()

{

//freopen(“zoo.in”,”r”,stdin);

//freopen(“zoo.out”,”w”,stdout);

scanf(“%d %d\n”,&N,&C);

for (int i=0;i<C;i++)

{

scanf(“%d “,&children[i].pos);

int love,hate;

scanf(“%d %d”,&love,&hate);

int pos;

for (int j=0;j<love;j++)

{

scanf(” %d”,&pos);

if (pos<children[i].pos) pos+=N;

children[i].love|=(1<<(pos-children[i].pos));

}

for (int j=0;j<hate;j++)

{

scanf(” %d”,&pos);

if (pos<children[i].pos) pos+=N;

children[i].hate|=(1<<(pos-children[i].pos));

}

scanf(“\n”);

//printf(“child%d’s data:\npos:%d\n”,i+1,children[i].pos);

//print(children[i].love,”love:”);printf(“\n”);

//print(children[i].hate,”hate:”);printf(“\n”);

}

for (int _start=0;_start<(1<<(SIGHT-1));_start++)

{

int start=_start<<1;

memset(f,0xf0,sizeof(f));

f[K(0)][start]=0;

int begin=0,end=-1;

for (int k=1;k<=N+1;k++)

{

while (children[begin].pos<k&&begin<C) begin++;

end=begin;

while (children[++end].pos==k) ;

for (int state=0;state<(1<<(SIGHT));state++)

{

int inc=0;

if (children[begin].pos==k)

for (int j=begin;j<end;j++)

if ((children[j].love&state)||(children[j].hate&(~state)))

inc++;

f[K(k)][state]=MAX(f[K(k-1)][(state<<1)&((1<<(SIGHT))-1)],

f[K(k-1)][((state<<1)|1)&((1<<(SIGHT))-1)])

+inc;

}

}

}

//printf(“runing time:%d\n”,clock());

//fclose(stdin);

//fclose(stdout);

return 0;

}