fork download 
import random
import socket
import sys
from copy import deepcopy

my_hostnames = ['N551J', 'F551C']

if socket.gethostname() in my_hostnames:
    sys.stdin = open('c1.in')
    sys.stdout = open('out.txt', 'w')


def read_str():
    return input()


def read_str_list():
    return list(input().split())


def read_int():
    return int(input())


def read_int_list():
    return list(map(int, input().split()))


def read_grid(n_rows):
    return [read_str() for i in range(n_rows)]


def read_float():
    return float(input())


def read_float_list():
    return list(map(float, input().split()))


def read_input():
    R, C = read_int_list()
    a = [read_int_list() for i in range(R)]
    return R, C, a


def random_input():
    M = 10 ** 6
    MR, MC = 5, 5
    MR, MC = 1, 1
    R, C = random.randint(1, MR), random.randint(1, MC)
    a = [[random.randint(1, M) for j in range(C)] for i in range(R)]
    return R, C, a


def judge(R, C, a):
    di = [0, 0, -1, 1]
    dj = [-1, 1, 0, 0]
    res = 0
    updated = True
    while updated:

        updated = []
        for i in range(R):
            for j in range(C):
                res += a[i][j]

        for i in range(R):
            for j in range(C):
                if a[i][j] == 0:
                    continue
                s = 0
                m = 0
                for k in range(4):
                    ii = i + di[k]
                    jj = j + dj[k]
                    while 0 <= ii < R and 0 <= jj < C and a[ii][jj] == 0:
                        ii += di[k]
                        jj += dj[k]
                    if 0 <= ii < R and 0 <= jj < C and a[ii][jj] > 0:
                        m += 1
                        s += a[ii][jj]
                if m * a[i][j] < s:
                    updated.append((i, j))
        for (i, j) in updated:
            a[i][j] = 0
    return res


def solve_it(R, C, a):
    neighbor = [[[(-1, -1) for k in range(4)] for j in range(C)] for i in range(R)]
    for i in range(R):
        last = None
        for j in range(C):
            if a[i][j]:
                if last is not None:
                    neighbor[i][j][0] = (i, last)
                    neighbor[i][last][1] = (i, j)
                last = j
    for j in range(C):
        last = None
        for i in range(R):
            if a[i][j]:
                if last is not None:
                    neighbor[i][j][2] = (last, j)
                    neighbor[last][j][3] = (i, j)
                last = i
    total = 0
    look = set()
    for i in range(R):
        for j in range(C):
            if a[i][j] == 0:
                continue
            total += a[i][j]
            look.add((i, j))

    res = 0
    eliminated = True
    while eliminated:
        eliminated = set()
        next_look = set()
        res += total
        for (i, j) in look:
            s = 0
            m = 0
            for k in range(4):
                ii, jj = neighbor[i][j][k]
                if 0 <= ii < R and 0 <= jj < C:
                    m += 1
                    s += a[ii][jj]
            if m * a[i][j] < s:
                eliminated.add((i, j))

        # print('look:', look)
        # print('eliminated:', eliminated)

        for (i, j) in eliminated:
            total -= a[i][j]

            for k in range(4):
                if neighbor[i][j][k] != (-1, -1):
                    next_look.add(neighbor[i][j][k])

            for k in [0, 2]:
                ii, jj = neighbor[i][j][k]
                iii, jjj = neighbor[i][j][k + 1]
                if (ii, jj) != (-1, -1):
                    neighbor[ii][jj][k + 1] = iii, jjj
                if (iii, jjj) != (-1, -1):
                    neighbor[iii][jjj][k] = ii, jj
        look = next_look
    return res


def debug():
    random.seed = 1
    n_steps = 10000
    for i in range(n_steps):
        R, C, a = random_input()
        aa = deepcopy(a)
        res = solve_it(R, C, a)
        expected = judge(R, C, aa)
        if res != expected:
            print(1)
            print(R, C)
            for i in range(R):
                print(*a[i])
        assert res == expected


def main():
    n_cases = int(input())
    for test_case in range(1, n_cases + 1):
        print(test_case, file=sys.stderr, end=' ')
        R, C, a = read_input()
        res = solve_it(R, C, a)
        print('Case #' + str(test_case) + ':', res)

    print(file=sys.stderr)


if __name__ == '__main__':
    # debug()
    main()
Runtime error #stdin #stdout #stderr 0.13s 23688KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Traceback (most recent call last):
  File "./prog.py", line 184, in <module>
    main()
  File "./prog.py", line 172, in main
    n_cases = int(input())
EOFError: EOF when reading a line
https://ideone.com/3ayUAK
language:
Python 3 nbc (python 3.7.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!