Submission #17591

#	Time	Username	Problem	Language	Result	Execution time	Memory
17591		comet	전봇대 (KOI13_pole)	C++98	100 / 100	61 ms	1864 KiB

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