-
Notifications
You must be signed in to change notification settings - Fork 0
/
a.py
85 lines (60 loc) · 1.97 KB
/
a.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#! /usr/bin/python3
import sys
rooms_len = None
row_len = None
rooms_weights = None
def two2one(row, col):
global row_len
return row_len * row + col
def get_bit(i, pos):
return i >> pos & 1
def set_bit(i, pos):
return i | (1 << pos)
def find_solution(k, closed_rooms):
global rooms_len
global row_len
global rooms_weights
if k == 0:
amount = 0
for i in range(rooms_len):
for j in range(row_len):
if get_bit(closed_rooms, two2one(i, j)) == 0:
amount += rooms_weights[i][j]
return amount
max_value = 0
for i in range(rooms_len):
if any([get_bit(closed_rooms, two2one(i, j)) for j in range(row_len)]):
continue
for j in range(row_len):
if get_bit(closed_rooms, two2one(i, j)) == 0:
if i - 1 >= 0 and get_bit(closed_rooms, two2one(i - 1, (j + 1) % 2)) == 1:
continue
if i + 1 < rooms_len and get_bit(closed_rooms, two2one(i + 1, (j + 1) % 2)) == 1:
continue
new_closed_rooms = set_bit(closed_rooms, two2one(i, j))
value = find_solution(k - 1, new_closed_rooms)
if value > max_value:
max_value = value
return max_value
def read_input(input_source):
rooms = []
n_and_k = input_source.readline().split()
N = int(n_and_k[0])
k = int(n_and_k[1])
if N == 0 and k == 0:
return N, k, rooms
for row in range(N):
two_rooms = list(map(lambda i: int(i), input_source.readline().split()))
rooms.append(two_rooms)
return N, k, rooms
f = open("Problem A/sample3.in", "r") # Time Limit Exceeded
while True:
N, k, rooms = read_input(f)
# N, k, rooms = read_input(sys.stdin)
if N == 0 and k == 0:
break
rooms_len = len(rooms)
row_len = len(rooms[0]) if rooms_len > 0 else 0
rooms_weights = rooms
print(find_solution(k, 0))
f.close()