Submission #752961

#	Time	Username	Problem	Language	Result	Execution time	Memory
752961		the_programmer_of_python	Fireworks (APIO16_fireworks)	Cpython 3	0 / 100	2078 ms	3000 KiB

fireworks

def distribute(a, f, l: list) -> list:
    l = iter(l)
    result = []
    try:
        result.append(f(a, next(l)))
    except StopIteration:
        return []
    for e in l:
        result.append(f(result[-1], e))
    return result

def find_bound(v, l: list, lower = True) -> int:
    lo, hi = 0, len(l)-1
    if lower:
        while lo <= hi:
            mi = (lo+hi)//2
            if l[mi] < v: lo = mi+1
            else: hi = mi-1
        return max(hi, 0)
    else:
        while lo <= hi:
            mi = (lo+hi)//2
            if l[mi] > v: hi = mi-1
            else: lo = mi+1
        return min(lo, len(l)-1)

def solve(lens: list[int]) -> int:
    lens = sorted(lens)

    #print('Lens: ', lens)

    prefix = distribute(0, int.__add__, lens)
    suffix = distribute(0, int.__add__, reversed(lens)); suffix.reverse()
    done = tuple(range(1, len(lens)+1))
    left = tuple(reversed(done))

    #print('Prefix: ', prefix)
    #print('Suffix: ', suffix)
    #print('Done: ', done)
    #print('Left: ', left)

    test = range(lens[0], lens[-1]+1)

    def check(n: int) -> int:
        before = find_bound(n, lens)
        after = find_bound(n, lens, False)

        #print('::', before, '->', after)

        n_before = done[before]
        n_after = left[after]
        #print(':#', n_before, '->', n_after)
        sum_before = prefix[before]
        sum_after = suffix[after]
        #print(':+', sum_before, '->', sum_after)

        #print(':*', n*n_before, '->', n*n_after)
        #print(':=', (n*n_before) - sum_before, sum_after - (n*n_after))

        return ((n*n_before) - sum_before) + (sum_after - (n*n_after))

    return min(map(check, test))

n, m = map(int, input().split())
assert n == 1
lens = [int(input().split()[1]) for i in range(m)]
print(solve(lens))

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45