Problem p03806 (python)

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = [INF] * 10000

    for i in range(1,2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        if h1[dif] > tc: h1[dif] = tc

    ans = h1[0]

    for i in range(1,2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        if dif == 0:
            ans = min(ans,tc)
        else:
            ans = min(ans,h1[dif]+tc)

    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        else:
            while h2[i][0] == h:
                if h != 0 and h2[i][0] != 0:
                    ans = min(ans,c+h2[i][1])
                i += 1
            continue
        break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & b:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        if h == h2[i][0] and (h != 0 and h2[i][0] != 0):
            ans = min(ans,c+h2[i][1])
        else:
            continue
        break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2,n):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        if h == h2[i][0] and (h != 0 and h2[i][0] != 0):
            ans = min(ans,c+h2[i][1])
        else:
            continue
        break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2,n):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        if h == h2[i][0] and (h != 0 and h2[i][0] != 0):
            ans = min(ans,c+h2[i][1])
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()