oj.uz

Submission #752961

# Submission time Handle Problem Language Result Execution time Memory
752961 2023-06-04T11:09:59 Z the_programmer_of_python Fireworks (APIO16_fireworks) Python 3
0 / 100
 2000 ms 3000 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3000 KB Output is correct
2 Execution timed out 2078 ms 2952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 2900 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3000 KB Output is correct
2 Execution timed out 2078 ms 2952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3000 KB Output is correct
2 Execution timed out 2078 ms 2952 KB Time limit exceeded
3 Halted 0 ms 0 KB -