Submission #2767976


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 PyPy3 (2.4.0)
Score 300
Code Size 394 Byte
Status AC
Exec Time 965 ms
Memory 87636 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 4
AC × 19
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 179 ms 38384 KB
sample_02.txt AC 178 ms 38256 KB
sample_03.txt AC 179 ms 38256 KB
sample_04.txt AC 179 ms 38256 KB
subtask_1_01.txt AC 178 ms 38256 KB
subtask_1_02.txt AC 361 ms 48748 KB
subtask_1_03.txt AC 309 ms 46468 KB
subtask_1_04.txt AC 500 ms 62320 KB
subtask_1_05.txt AC 723 ms 81904 KB
subtask_1_06.txt AC 767 ms 86100 KB
subtask_1_07.txt AC 965 ms 87636 KB
subtask_1_08.txt AC 803 ms 87252 KB
subtask_1_09.txt AC 785 ms 87252 KB
subtask_1_10.txt AC 777 ms 86864 KB
subtask_1_11.txt AC 777 ms 86864 KB