Submission #1171892

#TimeUsernameProblemLanguageResultExecution timeMemory
1171892IsamZemljište (COCI22_zemljiste)Pypy 3
0 / 70
145 ms51104 KiB
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)

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'Main.py'...

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

=======
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...