oj.uz

Submission #17596

# Submission time Handle Problem Language Result Execution time Memory
17596 2016-01-01T18:56:14 Z Namnamseo 전봇대 (KOI13_pole) C++14
100 / 100
 40 ms 1864 KB 
#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.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 2 ms 1864 KB Output is correct
3 Correct 4 ms 1864 KB Output is correct
4 Correct 4 ms 1864 KB Output is correct
5 Correct 4 ms 1864 KB Output is correct
6 Correct 4 ms 1864 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1864 KB Output is correct
2 Correct 38 ms 1864 KB Output is correct
3 Correct 32 ms 1864 KB Output is correct
4 Correct 33 ms 1864 KB Output is correct
5 Correct 38 ms 1864 KB Output is correct
6 Correct 37 ms 1864 KB Output is correct