oj.uz

Submission #23670

# Submission time Handle Problem Language Result Execution time Memory
23670 2017-05-18T15:09:12 Z leejseo 전봇대 (KOI13_pole) C++14
100 / 100
 39 ms 2292 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2292 KB Output is correct
2 Correct 0 ms 2292 KB Output is correct
3 Correct 0 ms 2292 KB Output is correct
4 Correct 0 ms 2292 KB Output is correct
5 Correct 0 ms 2292 KB Output is correct
6 Correct 0 ms 2292 KB Output is correct
7 Correct 0 ms 2292 KB Output is correct
8 Correct 0 ms 2292 KB Output is correct
9 Correct 0 ms 2292 KB Output is correct
10 Correct 0 ms 2292 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2292 KB Output is correct
2 Correct 0 ms 2292 KB Output is correct
3 Correct 0 ms 2292 KB Output is correct
4 Correct 0 ms 2292 KB Output is correct
5 Correct 0 ms 2292 KB Output is correct
6 Correct 0 ms 2292 KB Output is correct
7 Correct 0 ms 2292 KB Output is correct
8 Correct 0 ms 2292 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2292 KB Output is correct
2 Correct 0 ms 2292 KB Output is correct
3 Correct 3 ms 2292 KB Output is correct
4 Correct 3 ms 2292 KB Output is correct
5 Correct 0 ms 2292 KB Output is correct
6 Correct 0 ms 2292 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2292 KB Output is correct
2 Correct 39 ms 2292 KB Output is correct
3 Correct 26 ms 2292 KB Output is correct
4 Correct 29 ms 2292 KB Output is correct
5 Correct 23 ms 2292 KB Output is correct
6 Correct 23 ms 2292 KB Output is correct