Submission #17596

#	Time	Username	Problem	Language	Result	Execution time	Memory
17596		Namnamseo	전봇대 (KOI13_pole)	C++14	100 / 100	40 ms	1864 KiB

pole

#include <cstdio>
 
long long data[100010];
int n;
 
long long abs(long long x) { return x>0?x:-x; }
 
long long getVal(long long x){
    auto ret=0ll;
    int i;
    for(i=0;i<n;++i) ret+=abs(data[i]-i*x);
    return ret;
}
 
int main()
{
    scanf("%d",&n);
    int i;
    for(i=0;i<n;++i) scanf("%lld",data+i);
    long long l=0, r=1LL<<30, a,b;
    while(l+3<r){
        a=(l*2+r)/3;
        b=(l+2*r)/3;
        if(getVal(a)<getVal(b)){
            r=b;
        } else l=a;
    }
    long long j,minval=1LL<<60;
    for(j=l;j<=r;++j){
        a=getVal(j);
        if(minval>a) minval=a;
    }
    printf("%lld\n",minval);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37