oj.uz

답안 #4480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4480 2013-10-08T12:57:41 Z model_code 전봇대 (KOI13_pole) C++
100 / 100
 44 ms 2260 KB 
#include <stdio.h>
#include <algorithm>

#define MaxN 100000
#define abs(a) ((a)>0?(a):-(a))
#define get_min(a, b) ((a)<(b)?(a):(b))

int N;
int X[MaxN];

long long D, Ans;

struct bot {
	int x, index;
} Bot[MaxN];

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

long long get_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++) X[i] -= X[0];
	for (i=1; i<N; i++){
		Bot[i].x = X[i];
		Bot[i].index = i;
	}
	std::sort(Bot+1, Bot+N, compare);

	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].index){
			break;
		}
		t += Bot[i].index;
	}

	D = Bot[i].x / Bot[i].index;
	printf("%lld\n", get_min(get_cost(D), get_cost(D+1)));
//	printf("%lld\n", get_min(get_cost(976), get_cost(977)));
	return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2260 KB Output is correct
2 Correct 0 ms 2260 KB Output is correct
3 Correct 0 ms 2260 KB Output is correct
4 Correct 0 ms 2260 KB Output is correct
5 Correct 0 ms 2260 KB Output is correct
6 Correct 0 ms 2260 KB Output is correct
7 Correct 0 ms 2260 KB Output is correct
8 Correct 0 ms 2260 KB Output is correct
9 Correct 0 ms 2260 KB Output is correct
10 Correct 0 ms 2260 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2260 KB Output is correct
2 Correct 0 ms 2260 KB Output is correct
3 Correct 0 ms 2260 KB Output is correct
4 Correct 0 ms 2260 KB Output is correct
5 Correct 0 ms 2260 KB Output is correct
6 Correct 0 ms 2260 KB Output is correct
7 Correct 0 ms 2260 KB Output is correct
8 Correct 0 ms 2260 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2260 KB Output is correct
2 Correct 0 ms 2260 KB Output is correct
3 Correct 4 ms 2260 KB Output is correct
4 Correct 0 ms 2260 KB Output is correct
5 Correct 4 ms 2260 KB Output is correct
6 Correct 0 ms 2260 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 2260 KB Output is correct
2 Correct 32 ms 2260 KB Output is correct
3 Correct 36 ms 2260 KB Output is correct
4 Correct 32 ms 2260 KB Output is correct
5 Correct 36 ms 2260 KB Output is correct
6 Correct 28 ms 2260 KB Output is correct