fork download
copy 
  1. import random
  2. import socket
  3. import sys
  4. from copy import deepcopy
  5.  
  6. my_hostnames = ['N551J', 'F551C']
  7.  
  8. if socket.gethostname() in my_hostnames:
  9.     sys.stdin = open('c1.in')
  10.     sys.stdout = open('out.txt', 'w')
  11.  
  12.  
  13. def read_str():
  14.     return input()
  15.  
  16.  
  17. def read_str_list():
  18.     return list(input().split())
  19.  
  20.  
  21. def read_int():
  22.     return int(input())
  23.  
  24.  
  25. def read_int_list():
  26.     return list(map(int, input().split()))
  27.  
  28.  
  29. def read_grid(n_rows):
  30.     return [read_str() for i in range(n_rows)]
  31.  
  32.  
  33. def read_float():
  34.     return float(input())
  35.  
  36.  
  37. def read_float_list():
  38.     return list(map(float, input().split()))
  39.  
  40.  
  41. def read_input():
  42.     R, C = read_int_list()
  43.     a = [read_int_list() for i in range(R)]
  44.     return R, C, a
  45.  
  46.  
  47. def random_input():
  48.     M = 10 ** 6
  49.     MR, MC = 5, 5
  50.     MR, MC = 1, 1
  51.     R, C = random.randint(1, MR), random.randint(1, MC)
  52.     a = [[random.randint(1, M) for j in range(C)] for i in range(R)]
  53.     return R, C, a
  54.  
  55.  
  56. def judge(R, C, a):
  57.     di = [0, 0, -1, 1]
  58.     dj = [-1, 1, 0, 0]
  59.     res = 0
  60.     updated = True
  61.     while updated:
  62.  
  63.         updated = []
  64.         for i in range(R):
  65.             for j in range(C):
  66.                 res += a[i][j]
  67.  
  68.         for i in range(R):
  69.             for j in range(C):
  70.                 if a[i][j] == 0:
  71.                     continue
  72.                 s = 0
  73.                 m = 0
  74.                 for k in range(4):
  75.                     ii = i + di[k]
  76.                     jj = j + dj[k]
  77.                     while 0 <= ii < R and 0 <= jj < C and a[ii][jj] == 0:
  78.                         ii += di[k]
  79.                         jj += dj[k]
  80.                     if 0 <= ii < R and 0 <= jj < C and a[ii][jj] > 0:
  81.                         m += 1
  82.                         s += a[ii][jj]
  83.                 if m * a[i][j] < s:
  84.                     updated.append((i, j))
  85.         for (i, j) in updated:
  86.             a[i][j] = 0
  87.     return res
  88.  
  89.  
  90. def solve_it(R, C, a):
  91.     neighbor = [[[(-1, -1) for k in range(4)] for j in range(C)] for i in range(R)]
  92.     for i in range(R):
  93.         last = None
  94.         for j in range(C):
  95.             if a[i][j]:
  96.                 if last is not None:
  97.                     neighbor[i][j][0] = (i, last)
  98.                     neighbor[i][last][1] = (i, j)
  99.                 last = j
  100.     for j in range(C):
  101.         last = None
  102.         for i in range(R):
  103.             if a[i][j]:
  104.                 if last is not None:
  105.                     neighbor[i][j][2] = (last, j)
  106.                     neighbor[last][j][3] = (i, j)
  107.                 last = i
  108.     total = 0
  109.     look = set()
  110.     for i in range(R):
  111.         for j in range(C):
  112.             if a[i][j] == 0:
  113.                 continue
  114.             total += a[i][j]
  115.             look.add((i, j))
  116.  
  117.     res = 0
  118.     eliminated = True
  119.     while eliminated:
  120.         eliminated = set()
  121.         next_look = set()
  122.         res += total
  123.         for (i, j) in look:
  124.             s = 0
  125.             m = 0
  126.             for k in range(4):
  127.                 ii, jj = neighbor[i][j][k]
  128.                 if 0 <= ii < R and 0 <= jj < C:
  129.                     m += 1
  130.                     s += a[ii][jj]
  131.             if m * a[i][j] < s:
  132.                 eliminated.add((i, j))
  133.  
  134.         # print('look:', look)
  135.         # print('eliminated:', eliminated)
  136.  
  137.         for (i, j) in eliminated:
  138.             total -= a[i][j]
  139.  
  140.             for k in range(4):
  141.                 if neighbor[i][j][k] != (-1, -1):
  142.                     if neighbor[i][j][k] not in eliminated:
  143.                         next_look.add(neighbor[i][j][k])
  144.  
  145.         for (i, j) in eliminated:
  146.  
  147.             for k in [0, 2]:
  148.                 ii, jj = neighbor[i][j][k]
  149.                 iii, jjj = neighbor[i][j][k + 1]
  150.                 if (ii, jj) != (-1, -1):
  151.                     neighbor[ii][jj][k + 1] = iii, jjj
  152.                 if (iii, jjj) != (-1, -1):
  153.                     neighbor[iii][jjj][k] = ii, jj
  154.         look = next_look
  155.     return res
  156.  
  157.  
  158. def debug():
  159.     random.seed = 1
  160.     n_steps = 10000
  161.     for i in range(n_steps):
  162.         R, C, a = random_input()
  163.         aa = deepcopy(a)
  164.         res = solve_it(R, C, a)
  165.         expected = judge(R, C, aa)
  166.         if res != expected:
  167.             print(1)
  168.             print(R, C)
  169.             for i in range(R):
  170.                 print(*a[i])
  171.         assert res == expected
  172.  
  173.  
  174. def main():
  175.     n_cases = int(input())
  176.     for test_case in range(1, n_cases + 1):
  177.         print(test_case, file=sys.stderr, end=' ')
  178.         R, C, a = read_input()
  179.         res = solve_it(R, C, a)
  180.         print('Case #' + str(test_case) + ':', res)
  181.  
  182.     print(file=sys.stderr)
  183.  
  184.  
  185. if __name__ == '__main__':
  186.     # debug()
  187.     main()
  188.  
Runtime error #stdin #stdout #stderr 0.11s 23772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 187, in <module>
    main()
  File "./prog.py", line 175, in main
    n_cases = int(input())
EOFError: EOF when reading a line
https://ideone.com/A2Trcw
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!