Решение вступительных заданий schol.hh.ru 2022

from bisect import bisect_right
 
n, m, s = map(int, input().split())
a, b = [0], [0]
for _ in range(max(n, m)):
    x, y = input().split()
    if x != '-':
        a.append(a[-1] + int(x))
    if y != '-':
        b.append(b[-1] + int(y))
res = 0
for i in range(n + 1):
    x = s - a[i]
    if x >= 0:
        j = bisect_right(b, x) - 1
        res = max(res, i + j)
print(res)

from math import inf
import sys
 
sys.setrecursionlimit(15000)
 
 
def dfs(x, y):
    global coords
    if a[x][y] == 0:
        return
    a[x][y] = 0
    coords = min(coords[0], x), min(coords[1], y), max(coords[2], x), max(coords[3], y)
    for i in range(-1, 2):
        for j in range(-1, 2):
            if 0 <= x + i < m and 0 <= y + j < n:
                dfs(x + i, y + j)
 
 
n, m = map(int, input().split())
a =[list(map(int, input().split())) for _ in range(m)]
 
p = [[0] * (n + 1) for _ in range(m + 1)] # суммы в прямоугольнике
for i in range(m):
    for j in range(n):
        p[i + 1][j + 1] += p[i][j + 1] + p[i + 1][j] - p[i][j] + a[i][j]
 
regions = []
for i in range(m):
    for j in range(n):
        if a[i][j] == 1:
            coords = (inf, inf, -inf, -inf)
            dfs(i, j)
            x1, y1, x2, y2 = coords
            s = (x2 - x1 + 1) * (y2 - y1 + 1)
            count_r = p[x1][y1] + p[x2 + 1][y2 + 1] - p[x1][y2 + 1] - p[x2 + 1][y1]
            if count_r > 1:
                regions.append((s, count_r))
 
if not regions:
    print(0)
else:
    print(max(regions, key=lambda x: (x[1] / x[0], x[0]))[0])