Submission #2767771


Source Code Expand

Copy
def f(A, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
N = int(input())
A = [int(x) for x in input().split()]
left, right = -10**9, 10**9
while left + 2 < right:
    diff = (right - left) // 3
    m1 = left + diff
    m2 = m1 + diff
    if f(A, m1) > f(A, m2):
        left = m1
    else:
        right = m2
print(min(f(A, i) for i in range(left, right + 1)))

Submission Info

Submission Time
Task C - Linear Approximation
User n_knuu
Language Python (3.4.3)
Score 0
Code Size 394 Byte
Status TLE
Exec Time 2105 ms
Memory 25840 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 300
Status
AC × 4
AC × 12
TLE × 7
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt
Case Name Status Exec Time Memory
sample_01.txt AC 18 ms 3064 KB
sample_02.txt AC 18 ms 3064 KB
sample_03.txt AC 19 ms 3060 KB
sample_04.txt AC 18 ms 3060 KB
subtask_1_01.txt AC 18 ms 3064 KB
subtask_1_02.txt AC 719 ms 7092 KB
subtask_1_03.txt AC 637 ms 6708 KB
subtask_1_04.txt AC 1847 ms 14144 KB
subtask_1_05.txt TLE 2104 ms 22156 KB
subtask_1_06.txt TLE 2105 ms 24844 KB
subtask_1_07.txt TLE 2104 ms 25156 KB
subtask_1_08.txt TLE 2105 ms 25748 KB
subtask_1_09.txt TLE 2105 ms 25156 KB
subtask_1_10.txt TLE 2105 ms 25072 KB
subtask_1_11.txt TLE 2105 ms 25840 KB