Bit full search with Go

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

Bit full search with Go
Full bit search with Python
python bit full search
Confirm bit full search
Learn algorithms with Go @ Full search_Linear search method
Learn search with Python # 2bit search, permutation search
Easy bit full search (easy power set)
Python with Go
Bit full search and direct product set
Hello world with full features of Go language
Sequential search with Python
Binary search with python
Binary search with Python3
Database search with db.py
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Draw Bezier curves with Go
Operate Db2 container with Go
Getting Started with Go Assembly
Create / search / create table with PynamoDB
Connect to Postgresql with GO
Hot reload with Go + Air
Try implementing perfume with Go
I can't search with # google-map. ..
Search engine work with python
Search twitter tweets with python
Streamline web search with python
I want to do a full text search with elasticsearch + python
[Go] Search channel ID/user ID from channel name/user name with slack api
Learning by ABC173C (bit full search, copying of multidimensional list, one-dimensionalization of multidimensional list)
Solve the subset sum problem with a full search in Python
Learn algorithms with Go @ recursive call
Grid search of hyperparameters with Scikit-learn
GUI development with Fyne by Go
Go see whales with combinatorial optimization
Tips for running Go with docker
Upload & move GCS files with Go
First OSMnx ~ With shortest path search ~
Build mlpy with python3.3 (64bit) (windows 64bit)
Using Lambda with AWS Amplify with Go
Using cgo with the go command
Search for homeomorphic idioms with opencv
Metaprogram go with YAML + Mustache + go-generate
Use curl / jq library with Go
Twitter search client made with bottle
About bit full search that often appears in competition pros From the eyes of beginners with python
Operate Linux Network Namespace with Go
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search