Submission #4480

#	Time	Username	Problem	Language	Result	Execution time	Memory
4480		model_code	전봇대 (KOI13_pole)	C++98	100 / 100	44 ms	2260 KiB

pole

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37