Submission #1171895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171895		Isam	Zemljište (COCI22_zemljiste)	Pypy 3	0 / 70	144 ms	51100 KiB

Main

INF = 1e18 + 7


def get_cost(sm, a, b):
    return abs(sm - a) + abs(sm - b)


def get_sm(x1, x2, y1, y2, pref):
    return pref[x2][y2] - pref[x1][y2] - pref[x2][y1] + pref[x1][y1]


def main():
    r, s, a, b = map(int, input().split())
    if a > b:
        a, b = b, a

    c = [[0] * (s + 1) for _ in range(r + 1)]
    pref = [[0] * (s + 1) for _ in range(r + 1)]

    for i in range(1, r + 1):
        row = list(map(int, input().split()))
        for j in range(1, s + 1):
            c[i][j] = row[j - 1]
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + c[i][j]

    ans = pref[r][s]
    cur_cost = INF
    prev_cost = INF
    next_cost = INF

    for x1 in range(r + 1):
        for x2 in range(x1, r + 1):
            y1 = 0
            y2 = 0
            cur_cost = prev_cost = next_cost = INF

            while max(y1, y2) <= s:
                next_sm = get_sm(x1, x2, y1, y2 + 1, pref)
                next_cost = get_cost(next_sm, a, b)

                if next_cost > prev_cost:
                    y1 += 1
                else:
                    y2 += 1

                cur_sm = get_sm(x1, x2, y1, y2, pref)
                cur_cost = get_cost(cur_sm, a, b)

                if x1 != x2 or y1 != y2:
                    ans = min(ans, cur_cost)

                prev_cost = cur_cost

    print(ans)

main()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 46%)

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40