-
Notifications
You must be signed in to change notification settings - Fork 0
/
p149.py
53 lines (40 loc) · 1.1 KB
/
p149.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
#p149
import time
start = time.time()
def generate_table():
res = [0]*4000000
for i in range(1, 56):
res[i - 1] = ((100003 - 200003*i + 300007*i*i*i)%1000000) - 500000
for i in range(56, 4000000):
res[i - 1] = ((res[i - 25] + res[i - 56] + 1000000))%1000000 - 500000
return res
def check_horizontal(L, n):
"""
Returns the maximum possible sum for row n
"""
row = L[(2000*n):(2000*(n+1))]
sums = [0]*2000
sums[0] = row[0]
for i in range(1, len(row)):
sums[i] = max(row[i], row[i] + sums[i-1])
return max(sums)
def check_vertical(L, n):
"""
Returns the maximum possible sum for column n
"""
col = L[n:len(L):2000]
sums = [0]*2000
sums[0] = col[0]
for i in range(1, len(col)):
sums[i] = max(col[i], col[i] + sums[i-1])
return max(sums)
def check_diagonal1(L, n):
return None
def check_diagonal2(L, n):
return None
my_table = generate_table()
max_found = 0
for i in range(0, 2000):
max_found = max(max_found, check_vertical(my_table, i))
print("Solution", max_found)
print(time.time() - start)