Submission #23670

#	Time	Username	Problem	Language	Result	Execution time	Memory
23670		leejseo	전봇대 (KOI13_pole)	C++14	100 / 100	39 ms	2292 KiB

pole

#include <stdio.h>
#include <algorithm>
#define abs(a) ((a)>0?(a):-(a))
#define min(a, b) ((a)<(b)?(a):(b))
int N;
int X[100000];
long long D, Ans;
struct bot{
    int x, id;
} Bot[100000];

bool cmp(bot a, bot b){
    return (long long)a.x * (long long)b.id < (long long)b.x * (long long)a.id;
}

long long cost(long long d){
    int i;
    long long sum = 0;
    for (i=1; i<N; i++){
        sum += abs(i*d - X[i]);
    }
    return sum;
}

int main(void){
    int i;
    long long sum, t;
    scanf("%d", &N);
    for (i=0; i<N; i++) scanf("%d", &X[i]);
    for (i=1; i<N; i++){
        Bot[i].x = X[i];
        Bot[i].id = i;
    }
    std::sort(Bot+1, Bot+N, cmp);
    sum = N; sum = sum*(sum-1)/2;
    t = 0;
    for (i=1; i<N; i++){
        if (t+1 <= (sum+1)/2 && (sum+1)/2 <= t+Bot[i].id) break;
        t += Bot[i].id;
    }
    D = Bot[i].x / Bot[i].id;
    printf("%lld\n", min(cost(D), cost(D+1)));
    return 0;
}

Compilation message (stderr)

pole.cpp: In function 'int main()':
pole.cpp:28:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
pole.cpp:29:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0; i<N; i++) scanf("%d", &X[i]);
                                           ^

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37