Submission #1209087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209087		Boomyday	Remittance (JOI19_remittance)	Pypy 3	55 / 100	1100 ms	216136 KiB

remittance

import sys
from fractions import *

def main():
    input = sys.stdin.read
    data = input().split()

    n = int(data[0])
    X = [0] * n

    sa, sb = 0, 0
    index = 1
    for i in range(n):
        a = int(data[index])
        b = int(data[index + 1])
        index += 2
        sa += a
        sb += b
        X[i] = a - b

    if sb == 0:
        if sa == 0:
            sys.stdout.write("Yes\n")
        else:
            sys.stdout.write("No\n")
        return

    ans = [0] * n
    val = 0

    for i in range(1, n):
        val += X[i] * (1 << (i - 1))  # 2**(i-1)
    val += X[0] * (1 << (n - 1))  # 2**(n-1)

    mod = (1 << n) - 1  # 2**n - 1
    if val % mod != 0:
        sys.stdout.write("No\n")
        return

    ans[0] = val // mod
    if ans[0] < 0:
        sys.stdout.write("No\n")
        return

    for i in range(1, n):
        if (ans[i - 1] + X[i]) % 2 != 0:
            sys.stdout.write("No\n")
            return
        ans[i] = (ans[i - 1] + X[i]) // 2
        if ans[i] < 0:
            sys.stdout.write("No\n")
            return

    sys.stdout.write("Yes\n")

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'remittance.py'...

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

=======

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 0 / 45