답안 #17591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17591	2016-01-01T13:46:14 Z	comet	전봇대 (KOI13_pole)	C++	100 / 100	61 ms	1864 KB

pole

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int n;
ll a[100010];
double f(double x){
	double ret=0;
	for(int i=0;i<n;i++)ret+=fabs(1.0*a[i]-x*i);
	return ret;
}
ll f(ll x){
	ll ret=0;
	for(ll i=0;i<n;i++)ret+=abs((ll)a[i]-x*i);
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	double lo=0,hi=1e9,z0,z1;
	for(int i=0;i<100;i++){
		z0=(lo*2+hi)/3.0,z1=(lo+hi*2)/3.0;
		if(f(z0)<f(z1))hi=z1;
		else lo=z0;
	}
	ll x=hi;
	printf("%lld",min(f(x),f(x+1)));
}

Subtask #1

11.0 / 11.0

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

Subtask #2

21.0 / 21.0

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

Subtask #3

31.0 / 31.0

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

Subtask #4

37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	1864 KB	Output is correct
2	Correct	59 ms	1864 KB	Output is correct
3	Correct	51 ms	1864 KB	Output is correct
4	Correct	59 ms	1864 KB	Output is correct
5	Correct	44 ms	1864 KB	Output is correct
6	Correct	49 ms	1864 KB	Output is correct