oj.uz

Submission #17591

# Submission time Handle Problem Language Result Execution time Memory
17591 2016-01-01T13:46:14 Z comet 전봇대 (KOI13_pole) C++
100 / 100
 61 ms 1864 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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