Submission #3249296


Source Code Expand

#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<utility>
#include<functional>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
#include<numeric>


#define FOR(i, a, b) for(int i=a; i<b; i++)
#define COUT(a) cout << a << endl;

using namespace std;
using Int = long long;
using P = pair<Int, Int>;

vector<Int> A;

Int f(Int x){
    Int sum = 0;
    FOR(i, 0, A.size()){
        sum += abs(A[i] - x) ;
    }
    return sum;
}

int main(){
    Int N;
    cin >> N;

    A = vector<Int>(N);
    
    FOR(i, 0, N){
        cin >> A[i];
    }

    Int n = 0;
    transform(begin(A),
    end(A), begin(A), [&](Int x){n++; return x-n;});

    sort(begin(A), end(A));

    Int x = A[A.size()/2];

    Int y = f(x);
    Int z = f(x+1);

    COUT(min(y, z));
    
}

Submission Info

Submission Time
Task C - Linear Approximation
User poifull10
Language C++14 (GCC 5.4.1)
Score 300
Code Size 848 Byte
Status AC
Exec Time 93 ms
Memory 1792 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 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 18 ms 512 KB
subtask_1_03.txt AC 14 ms 512 KB
subtask_1_04.txt AC 41 ms 1024 KB
subtask_1_05.txt AC 71 ms 1664 KB
subtask_1_06.txt AC 80 ms 1792 KB
subtask_1_07.txt AC 93 ms 1792 KB
subtask_1_08.txt AC 83 ms 1792 KB
subtask_1_09.txt AC 81 ms 1792 KB
subtask_1_10.txt AC 82 ms 1792 KB
subtask_1_11.txt AC 82 ms 1792 KB