Donuts Procon Challenge B --Tokyo 7th Sisters https://atcoder.jp/contests/donuts-2015/tasks/donuts_2015_2
package main
import(
"fmt"
"bufio"
"os"
"strconv"
"strings"
"go/types"
"go/token"
)
var rdr=bufio.NewReaderSize(os.Stdin,10000000)
func readLine()string{
l,_,_:=rdr.ReadLine()
return string(l)
}
func readInts()[]int{
s:=strings.Split(readLine()," ")
res:=[]int{}
for i:=0;i<len(s);i++{
i,_:=strconv.Atoi(s[i])
res=append(res,i)
}
return res
}
func chmax(x,y int)int{if x>=y{return x}else{return y}}
func contains(x int,sl []int)bool{
res:=false
for i:=0;i<len(sl);i++{
if sl[i]==x{
res=true
break
}
}
return res
}
func main(){
tmp:=readInts()
n,m:=tmp[0],tmp[1]
A:=readInts()
B:=[]int{}
I:=[][]int{}
for i:=0;i<m;i++{
tmp:=readInts()
B=append(B,tmp[0])
I=append(I,tmp[2:])
for j:=0;j<tmp[1];j++{
I[i][j]--
}
}
//fmt.Println(n,A)
//fmt.Println(B)
//fmt.Println(I)
ans:=0
for bits:=0;bits<(1<<uint64(n));bits++{
score:=0
combo:=[]int{}
for i:=0;i<n;i++{
if (bits>>uint64(i))&1==1{
score+=A[i] //The score of the person
combo=append(combo,i)
}
}
if len(combo)>9{
continue
}
cnt:=0
//bonus:=0
for i:=0;i<m;i++{
cnt=0
for j:=0;j<len(combo);j++{
if contains(combo[j],I[i]){
cnt++
}
}
if cnt>=3{
score+=B[i]
//bonus+=B[i]
}
}
//if score==6100{fmt.Println("score",score,"combo",combo,"cnt",cnt,"B[i]",bonus)}
ans=chmax(ans,score)
}
fmt.Println(ans)
}
Recommended Posts