Problem:


Score : 300 points

Problem Statement

Joisino is planning to open a shop in a shopping street.

Each of the five weekdays is divided into two periods, the morning and the evening. For each of those ten periods, a shop must be either open during the whole period, or closed during the whole period. Naturally, a shop must be open during at least one of those periods.

There are already N stores in the street, numbered 1 through N.

You are given information of the business hours of those shops, F_{i,j,k}. If F_{i,j,k}=1, Shop i is open during Period k on Day j (this notation is explained below); if F_{i,j,k}=0, Shop i is closed during that period. Here, the days of the week are denoted as follows. Monday: Day 1, Tuesday: Day 2, Wednesday: Day 3, Thursday: Day 4, Friday: Day 5. Also, the morning is denoted as Period 1, and the afternoon is denoted as Period 2.

Let c_i be the number of periods during which both Shop i and Joisino's shop are open. Then, the profit of Joisino's shop will be P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}.

Find the maximum possible profit of Joisino's shop when she decides whether her shop is open during each period, making sure that it is open during at least one period.

Constraints

1≤N≤100

0≤F_{i,j,k}≤1

For every integer i such that 1≤i≤N, there exists at least one pair (j,k) such that F_{i,j,k}=1.

-10^7≤P_{i,j}≤10^7

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
F_{1,1,1} F_{1,1,2} ... F_{1,5,1} F_{1,5,2}
:
F_{N,1,1} F_{N,1,2} ... F_{N,5,1} F_{N,5,2}
P_{1,0} ... P_{1,10}
:
P_{N,0} ... P_{N,10}

Output

Print the maximum possible profit of Joisino's shop.

Sample Input 1

1
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2

Sample Output 1

8

If her shop is open only during the periods when Shop 1 is opened, the profit will be 8, which is the maximum possible profit.

Sample Input 2

2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1

Sample Output 2

-2

Note that a shop must be open during at least one period, and the profit may be negative.

Sample Input 3

3
1 1 1 1 1 1 0 0 1 1
0 1 0 1 1 1 1 0 1 0
1 0 1 1 0 1 0 1 0 1
-8 6 -2 -8 -8 4 8 7 -6 2 2
-9 2 0 1 7 -5 0 -2 -6 5 5
6 -6 7 -9 6 -5 8 0 -9 -7 -7

Sample Output 3

23



Sample input:
1
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2


Sample output:
8

Submission status: Accepted

Solution code:
N = int(input())
F = tuple(tuple(map(int, input().split())) for _ in range(N))
P = tuple(tuple(map(int, input().split())) for _ in range(N))
ans = -float("inf")
for n in range(1, 1024):
    indices = [0] * N
    for i in range(N):
        for j in range(10):
            if (n >> (9 - j)) & 1:
                indices[i] += F[i][j]
    ans = max(ans, sum(profit[idx] for profit, idx in zip(P, indices)))
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]

pattern = []
for i in range(2 ** 10):
    temp = [0] * 10
    for j in range(10):
        if (i >> j) & 1:
            temp[j] = 1
    pattern.append(temp)
pattern.remove([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])

ans = -10 ** 10
for i in range(len(pattern)):
    my_store = pattern[i]
    profit = 0
    for j in range(n):
        same_open = [x & y for (x, y) in zip(pattern[i], f[j])]
        profit += p[j][sum(same_open)]
    ans = max(ans, profit)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
FF = [list(map(int, input().split())) for _ in range(N)]
P = [list(map(int, input().split())) for _ in range(N)]

ans = -10**10
q = deque()
q.append([])
while q:
  x = q.pop()
  if len(x) == 10:
    tmp = 0
    i = 0
    while i < N:
      tmp += P[i][sum([x[j]*FF[i][j] for j in range(10)])]
      i += 1
    ans = max(ans, -10**10 if sum(x) < 1 else tmp)
  else:
    q.append(x+[0])
    q.append(x+[1])
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
F1=[]
F2=[]
for i in range(N):
    F=list(map(int,input().split()))
    F1.append(F[::2])
    F2.append(F[1::2])
P=[list(map(int,input().split())) for _ in range(N)]

ans=-float("inf")
for i in range(1,2**10):
    F_am=[0]*5
    F_pm=[0]*5
    for j in range(5):
        F_am[j]=i%2
        i//=2
        F_pm[j]=i%2
        i//=2
    c=[0]*N
    for j in range(N):
        for k in range(5):
            if F_am[k]==1 and F1[j][k]==1:
                c[j]+=1
            if F_pm[k]==1 and F2[j][k]==1:
                c[j]+=1
    val=0
    for j in range(N):
        val+=P[j][c[j]]
    ans=max(ans,val)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Fs = []
for _ in range(N):
    Fs.append(list(map(int, input().split())))

Ps = []
for _ in range(N):
    Ps.append(list(map(int, input().split())))


def calc(isOpen):
    global ans
    isAllClose = True
    for i in range(10):
        if isOpen[i]:
            isAllClose = False

    if isAllClose:
        return

    rieki = 0
    for i in range(N):
        count = 0
        for j in range(10):
            if Fs[i][j] and isOpen[j]:
                count += 1

        rieki += Ps[i][count]

    ans = max(ans, rieki)


def search(isOpen):
    if len(isOpen) == 10:
        calc(isOpen)
    else:
        search(isOpen + [True])
        search(isOpen + [False])


ans = -float('inf')
search([])

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    F=[]
    for _ in range(N):
        F.append(list(map(int,input().split())))
    P=[]
    for _ in range(N):
        P.append(list(map(int,input().split())))
    ans=-INF
    for i in range(1,2**10):
        tmp=0
        l=[0]*N
        for j in range(10):
            if (i>>j)&1:
                for k in range(N):
                    l[k]+=F[k][j]
        for k in range(N):
            tmp+=P[k][l[k]]
        ans=max(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
f=[list(map(int,input().split())) for _ in range(n)]
p=[list(map(int,input().split())) for _ in range(n)]
from itertools import product as pr
x=-10**9
for ch in list(pr([0,1],repeat=10)):
  if 1 not in ch:
    continue
  s=0
  for j in range(n):
    c=0
    t=f[j]
    for k in range(10):
      if ch[k] and t[k]:
        c+=1
    s+=p[j][c]
  x=max(x,s)
print(x)

Submission status: Accepted

Solution code:
import  itertools
n=int(input())
F=[]
for i in range(n):
    a=list(map(int,input().split()))
    F.append(a)
P=[]
for i in range(n):
    a=list(map(int,input().split()))
    P.append(a)

ans=-float("inf")

def j(a):
    tmp=0
    for i in range(n):
        cnt=0
        for j in range(10):
            if F[i][j]==1 and a[j]==1:
                cnt+=1
        tmp+=P[i][cnt]
    return tmp

for pa in itertools.product([0,1],repeat=10):
    pa=list(pa)
    if not pa.count(1)==0:
        ans=max(ans,j(pa))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    F = Scanner.int_list_list(N)
    P = Scanner.int_list_list(N)
    ans = -INF
    for i in range(1, 1 << 10):
        o = [False for _ in range(10)]
        for j in range(10):
            if i >> j & 1:
                o[j] = True
        t = [0 for _ in range(N)]
        for j in range(10):
            if not o[j]:
                continue
            for k in range(N):
                t[k] += F[k][j]
        tmp = 0
        for j in range(N):
            tmp += P[j][t[j]]
        ans = max(ans, tmp)
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

S = []
for _ in range(N):
    s = int(''.join(input().split()), 2)
    S.append(s)

P = []
for _ in range(N):
    p = [int(i) for i in input().split()]
    P.append(p)

ans = -10**20
for i in range(1, 2 ** 10):
    c = 0
    for j in range(N):
        c += P[j][bin(S[j] & i).count('1')]
    ans = max(ans, c)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

bit = [0, 1]

lst = list(product(bit, repeat=10))

n = int(input())
F = [list(map(int, input().split())) for i in range(n)]
P = [list(map(int, input().split())) for j in range(n)]

res = -1 << 30
for v in lst:
	if v.count(0) == 10: continue
	fund = 0
	for i in range(n):
		cnt = 0
		for x in range(10):
			if F[i][x] == 1 and v[x] == 1:
				cnt += 1
		fund += P[i][cnt]
	res = max(res, fund)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
F = [[] * 10 for _ in range(n)]
P = [[] * 10 for _ in range(n)]

for i in range(n):
	F[i] = list(map(int, input().split()))

for i in range(n):
	P[i] = list(map(int, input().split()))


res = -1<<30
for item in range(1, 1 << 10):
	fund = 0
	for i in range(n):
		cnt = 0
		for x in range(10):
			if item >> x & 1 and F[i][x] == 1:
				cnt += 1
		fund += P[i][cnt]
	res = max(res, fund)

print(res)

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())

F = [[] for _ in range(N)]
for i in range(N):
    F[i] = list(map(int, sys.stdin.readline().rstrip().split()))

P = []
for i in range(N):
    P.append(list(map(int, sys.stdin.readline().rstrip().split())))

ans = -float("inf")
for i in range(1, 1<<10):
    score = 0
    for j in range(N):
        count = 0
        for k in range(10):
            # print(i & (1 << k))
            if i & (1<<k) and F[j][k] == 1:
                count += 1
        # print("count", count)
        score += P[j][count]
    # print(score)
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
f=[list(map(int,input().split())) for _ in range(n)]
p=[list(map(int,input().split())) for _ in range(n)]
ans=-pow(10,9)
# bit全探索
for i in range(1,2**10):
  s=[]
  for j in range(10):
    if ((i>>j) & 1):#0~9の時間のうち、お姉ちゃんの店が営業する時間
      s.append(j)
  ansi=0
  for j in range(n):
    ansi+=p[j][sum([f[j][si] for si in s])]
  ans=max(ans,ansi)
print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
n = int(input())
opens = []
for i in range(n):
    opens.append(list(ma()))
P = []
for i in range(n):
    P.append(list(ma()))

ans = -10**9

for i in range(2**10):
    tmp = 0
    cnts = [0]*n
    if i==0:continue
    for j in range(10):
        if i>>j &1:
            for shop in range(n):
                if opens[shop][j] ==1:
                    cnts[shop]+=1
    for shop in range(n):
        tmp+=P[shop][cnts[shop]]

    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    F=[]
    for i in range(N):
        f=int("".join(readline().strip().split(" ")),2)
        F.append(f)
    P=[]
    for i in range(N):
        p=list(map(int,readline().split()))
        P.append(p)
    
    max_res=float("-inf")
    for output in range(1,1<<10):
        res=0
        for j in range(N):
            c=bin(output&F[j]).count("1")
            res+=P[j][c]
        max_res=max(res,max_res)

    print(max_res)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
f = [[int(i) for i in input().split()] for _ in range(n)]
p = [[int(i) for i in input().split()] for _ in range(n)]
ans = -float("inf")
for x in range(1,1<<10):
    res = 0
    for i in range(n):
        cnt = 0
        for j in range(10):
            if x>>j&1 and f[i][j]: cnt += 1
        res += p[i][cnt]
    ans = max(ans,res)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    F=[]
    for i in range(N):
        f=list(map(int,readline().split()))
        F.append(f)
    P=[]
    for i in range(N):
        p=list(map(int,readline().split()))
        P.append(p)
    
    max_res=-float("inf")
    for i in range(1<<10):
        if i==0:
            continue
        else:
            output=[]
            for j in range(10):
                if(i>>j)&1:
                    output.append(j)

            oc=[0]*10  #open or close
            for j in output:
                oc[j]=1
            
            res=0
            for j in range(N):
                c=0
                for k in range(10):
                    if oc[k]==1 and F[j][k]==1:
                        c+=1
                res+=P[j][c]
            max_res=max(res,max_res)

    print(max_res)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import product
    import heapq

    n = int(input())
    f = [list(map(int, input().split())) for _ in range(n)]
    p = [list(map(int, input().split())) for _ in range(n)]

    l = [[0, 0], [1, 0], [0, 1], [1, 1]]
    r = range(4)
    ans = []
    heapq.heapify(ans)
    for c in product(r, r, r, r, r):
        v = [l[i] for i in c]
        s = sum(v, [])
        if sum(s) == 0:
            continue
        t = sum(y[sum([i * j for i, j in zip(s, x)])] for x, y in zip(f, p))
        heapq.heappush(ans, -t)

    print(-1 * heapq.heappop(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import product
    n = int(input())
    f = [list(map(int, input().split())) for _ in range(n)]
    p = [list(map(int, input().split())) for _ in range(n)]

    l = [[0, 0], [1, 0], [0, 1], [1, 1]]
    r = range(4)
    ans = - 10 ** 9
    for c in product(r, r, r, r, r):
        v = [l[i] for i in c]
        s = sum(v, [])
        if sum(s) == 0:
            continue
        t = 0
        for x, y in zip(f, p):
            m = sum([i * j for i, j in zip(s, x)])
            t += y[m]

        ans = max(ans, t)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
F = [tuple(map(int, input().split())) for _ in range(n)]
P = [tuple(map(int, input().split())) for _ in range(n)]
ans = -10 ** 18

for i in range(1,2**10):
  tmp = 0
  lst = [0]*n
  for j in range(10): #時間帯
        if (i >> j) & 1: #開けるとした時
            for k in range(n):
                lst[k] += F[k][j]
  for k in range(n):
      tmp += P[k][lst[k]]
  ans = max(ans, tmp)
 
 
print (ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

def abc080_c_np():
    N = int(readline())  # 他店の数
    # 他店の営業パターン：店→日付→営業01
    F = np.zeros((N, 10), dtype=np.int8)
    for i in range(N): F[i] = readline().split()
    # 他店と何回重なると利益がどうなるか：店→重複回数→利益
    P = np.zeros((N, 11), dtype=np.int32)
    for i in range(N): P[i] = readline().split()
    ans = -10**12  # 最悪 100 * -10**7

    # bit全探索
    from itertools import product
    for mask in product(range(2), repeat=10):
        if mask.count(1) == 0: continue
        profit = 0
        mask_np = np.array(mask, np.int8)
        for i in range(N):
            # 他店iの営業パターンと、自店の営業パターンmaskと、の要素積は、重複する営業日
            overlap = np.logical_and(F[i,:], mask_np).sum()
            profit += P[i, overlap]
        ans = max(profit, ans)
    print(ans)

abc080_c_np()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

def abc080_c_np():
    N = int(readline())  # 他店の数
    # 他店の営業パターン：店→日付→営業01
    F = np.zeros((N, 10), dtype=np.int8)
    for i in range(N): F[i] = readline().split()
    # 他店と何回重なると利益がどうなるか：店→重複回数→利益
    P = np.zeros((N, 11), dtype=np.int32)
    for i in range(N): P[i] = readline().split()
    ans = -10**12  # 最悪 100 * -10**7

    # bit全探索
    from itertools import product
    for mask in product(range(2), repeat=10):
        if mask.count(1) == 0: continue
        profit = 0
        mask_np = np.array(mask, np.int8)
        for i in range(N):
            # 他店iの営業パターンと、自店の営業パターンmaskと、の要素積は、重複する営業日
            overlap = np.multiply(F[i,:], mask_np).sum()
            profit += P[i, overlap]
        ans = max(profit, ans)
    print(ans)

abc080_c_np()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

def abc080_c():
    N = int(readline())  # 他店の数
    # 他店の営業パターン：店→日付→営業01
    F = np.zeros((N, 10), dtype=np.int8)
    for i in range(N): F[i] = readline().split()
    # 他店と何回重なると利益がどうなるか：店→重複回数→利益
    P = np.zeros((N, 11), dtype=np.int32)
    for i in range(N): P[i] = readline().split()
    ans = -10**12  # 最悪 100 * -10**7

    # bit全探索
    from itertools import product
    for mask in product(range(2), repeat=10):
        if mask.count(1) == 0: continue
        profit = 0
        for i in range(N):
            # 他店iの営業パターンと、自店の営業パターンmaskと、の要素積は、重複する営業日
            overlap = np.multiply(F[i,:], mask).sum()
            profit += P[i, overlap]
        ans = max(profit, ans)
    print(ans)

abc080_c()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def abc080_c():
    N = int(readline())  # 他店の数
    # 他店の営業パターン：店→日付→営業01
    F = [list(map(int, readline().split())) for _ in range(N)]
    # 他店と何回重なると利益がどうなるか：店→重複回数→利益
    P = [list(map(int, readline().split())) for _ in range(N)]
    ans = -10**12  # 最悪 100 * -10**7

    # bit全探索
    from itertools import product
    from operator import mul
    for mask in product(range(2), repeat=10):
        if mask.count(1) == 0: continue
        profit = 0
        for i in range(N):
            # 他店iの営業パターンと、自店の営業パターンmaskと、の要素積は、重複する営業日
            #overlap = sum(x * y for x, y in zip(F[i], mask))
            overlap = sum(map(mul, F[i], mask))
            profit += P[i][overlap]
        ans = max(profit, ans)
    print(ans)

abc080_c()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

def abc080_c():
    N = int(readline())  # 他店の数
    # 他店の営業パターン：店→日付→営業01
    F = np.array([list(map(int, readline().split())) for _ in range(N)], dtype=np.int32)
    # 他店と何回重なると利益がどうなるか：店→重複回数→利益
    P = np.array([list(map(int, readline().split())) for _ in range(N)], dtype=np.int32)
    ans = -10**12  # 最悪 100 * -10**7

    # bit全探索
    from itertools import product
    for mask in product(range(2), repeat=10):
        if mask.count(1) == 0: continue
        profit = 0
        for i in range(N):
            # 他店iの営業パターンと、自店の営業パターンmaskと、の要素積は、重複する営業日
            overlap = np.multiply(F[i,:], mask).sum()
            profit += P[i, overlap]
        ans = max(profit, ans)
    print(ans)

abc080_c()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
n = int(input())
f = [list(map(int, input().split())) for _ in [0]*n]
p = [list(map(int, input().split())) for _ in [0]*n]

m = -float("INF")
from itertools import*
for j in product([0, 1], repeat=10):
    if sum(j) == 0:
        continue
    t = 0
    for i, k in enumerate(f):
        t += p[i][sum(np.array(j) & np.array(k))]
    m = max(t, m)
print(m)

Submission status: Accepted

Solution code:
n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]

ans=-10**18
for i in range(1<<10):
  if i==0:continue
  tp=0
  for j in range(n):
    tcnt=0
    for k in range(10):
      if i&(1<<k):tcnt+=f[j][k]
    tp+=p[j][tcnt]
  ans=max(ans,tp)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]

ans = []
stk = [[0] * n]

for i in range(10):
    for j in range(len(stk)):
        total = 0
        arr = []
        for k in range(n):
            open_shops = stk[j][k] + f[k][i]
            arr.append(open_shops)
            total += p[k][open_shops]
        ans.append(total)
        stk.append(arr)

print(max(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
f = [list(map(int,input().split()))for i in range(n)]
p = [list(map(int,input().split()))for i in range(n)]
ans = -float('inf')
for i in range(1,2**10):
    bin = format(i,'b').zfill(10)
    c = [0]*n
    for j in range(n):
        for k in range(10):
            if bin[k] == '1' and f[j][k] == 1:
                c[j] += 1
    r = 0
    for i in range(n):
        r += p[i][c[i]]
    ans = max(ans, r)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
f = [list(map(int, input().split())) for i in range(n)]
p = [list(map(int, input().split())) for i in range(n)]
# print("p =", p)
ans = -INF
for i in range(1 << 10):
    if i == 0:
        continue
    bit = bin(i)[2:].zfill(10)
    # print("bit =", bit)
    profit = 0

    for j in range(n):
        cnt = 0 
        for k in range(10):
            if bit[k] == "1" and f[j][k] == 1:
                cnt += 1
        profit += p[j][cnt]
    ans = max(ans, profit)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]

ans = -float("inf")
for i in range(1,1 << 10):
    l = [0]*n
    for j in range(10):
        #bin(i)をj桁シフトして0001と&をとる　＝　j桁目が1なら採用
        if ((i >> j) & 1) == 1:
            # fが一日どうか
            for k in range(n):
                if f[k][j] == 1:
                    l[k]+= 1
    
    ansi = 0
    for m in range(n):
        ansi += p[m][l[m]]
    ans = max(ans,ansi)
print(ans)

Submission status: Accepted

Solution code:
import sys

# import math
# import bisect

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
# MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d1 = []
    d2 = []
    for i in range(n):
        t = sys.stdin.readline().split()
        tmp = "".join(t)
        d1.append(int(tmp))
    for i in range(n):
        d2.append(na())

    ans = -10**9
    for i in range(1, 2 ** 10):
        cost = 0
        for j in range(n):
            b = i & int(str(d1[j]),2)
            b = list(format(b, "b"))
            b = [int(n) for n in b]
            b = sum(b)
            cost += d2[j][b]

        ans = max(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations

    N = int(input())
    F = []
    for _ in range(N):
        t = 0
        for j, b in enumerate(map(int, input().split())):
            if b:
                t |= (1 << j)
        F.append(t)
    # F[i]:=店舗iの営業時間情報
    P = [list(map(int, input().split())) for _ in range(N)]
    # P[i]:=店舗iと営業時間が重なる個数に対する利益

    ans = -10 ** 9 - 1
    for open_ in range(1, 10 + 1):
        for comb in combinations(range(10), r=open_):
            t = 0
            for j in comb:
                t |= (1 << j)

            p = 0
            for i, f in enumerate(F):
                x = bin(t & f).count('1')
                p += P[i][x]

            ans = max(ans, p)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = -inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
F = [list(map(int,input().split())) for i in range(n)]
P = [list(map(int,input().split())) for i in range(n)]
for bit in range(1,2**10):
  tmp = 0
  for i in range(n):
    count = 0
    for k in range(10):
      if bit >> k & 1:
        count += F[i][k]
    tmp += P[i][count]
  mans = max(mans,tmp)
print(mans)

Submission status: Accepted

Solution code:
n = int(input())
f = []
for _ in range(n):
    f.append(list(map(int, input().split())))
p = []
for _ in range(n):
    p.append(list(map(int, input().split())))

ans = -10**9
for i in range(1, 2**10):
    profit = 0
    for ff, pp in zip(f, p):
        cnt = 0
        for j in range(10):
            cnt += ((i>>j)&1)&ff[j]
        profit += pp[cnt]
    ans = max(ans, profit)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())

F=[]
for i in range(N):
    f=list(map(int, input().split()))
    F.append(f)

P=[]
for i in range(N):
    p=list(map(int, input().split()))
    P.append(p)

F=np.array(F)
P=np.array(P)

ans=-np.inf

for b in range(1,2**10):
    now=0
    L=np.zeros(N)
    for i in range(10):
        if b>>i&1==1:
            L+=F[:,i]
    for i in range(N):
        now+=P[i,int(L[i])]
    ans=max(ans, now)

print(ans)