Ruudukko

import random
import bisect

# n = 100
# rows = []
# for i2 in range(n):
#     rows.append(random.sample(range(1, n*n+1), n*n))

# n = 3
# rows = [
#     [2,1,3], 
#     [1,1,1], 
#     [9,2,7]
# ]

n = int(input())
rows = []
for i in range(n):
    rows.append([int(x) for x in input().split(" ")])

unique_numbers = set()
for i2 in range(n):
    for j1 in range(n):
        unique_numbers.add(rows[i2][j1])

def get_coordinates_of(lambda_function):
    coords = []
    for i in range(n):
        for j in range(n):
            if lambda_function(rows[i][j]):
                coords.append((i, j))
    return coords

coords_per_number = {}
for i in range(n):
    for j in range(n):
        num = rows[i][j]
        if(num not in coords_per_number):
            coords_per_number[num] = []
        coords_per_number[num].append((i, j))

unique_numbers = sorted(unique_numbers)

cache = {}
for num in unique_numbers:
    coords = coords_per_number[num]
    for c in coords:
        lines = []
        for j1 in range(n):
            if rows[c[0]][j1] < num:
                lines.append((c[0], j1))
            if rows[j1][c[1]] < num:
                lines.append((j1, c[1]))

        cache[c] = sum([cache[x] for x in lines]) + 1


print(sum(cache.values()) % (10**9 + 7))

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED