oj.uz

Submission #4948

# Submission time Handle Problem Language Result Execution time Memory
4948 2014-01-23T13:17:32 Z hana5505 전봇대 (KOI13_pole) C++
100 / 100
 52 ms 3044 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int ar[100001];
struct pp{
    int x;
    double y;
}st[100001];
long long cnt=0,s=0,ans=0,ans2=0;
long long ab(long long k){
    if(k<0) return -k;
    return k;
}
bool cmp(struct pp a,struct pp b){
    return a.y<b.y;
}
int main()
{
    int i,n,t1,t2;
 
    scanf("%d",&n);
 
    for(i=0;i<n;i++){
        scanf("%d",&ar[i]);
        if(i!=0){
            st[i].x=i;
            st[i].y=(double)ar[i]/i;
            cnt+=i;
        }
    }
    sort(st+1,st+n,cmp);
 
    if(cnt%2==1){
        for(i=1;i<n;i++){
            s+=st[i].x;
            if(s>=(cnt+1)/2){
                t1=(int)st[i].y;
                t2=(int)st[i].y+1;
                break;
            }
        }
    }
    else{
        for(i=1;i<n;i++){
            s+=st[i].x;
            if(s>=cnt/2){
                t1=(int)st[i].y;
                t2=(int)st[i].y+1;
                break;
            }
        }
    }
 
    for(i=1;i<n;i++) ans+=ab((long long)ar[i]-(long long)i*t1);
    for(i=1;i<n;i++) ans2+=ab((long long)ar[i]-(long long)i*t2);
    if(ans2<ans) printf("%lld",ans2);
    else printf("%lld",ans);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3044 KB Output is correct
2 Correct 0 ms 3044 KB Output is correct
3 Correct 0 ms 3044 KB Output is correct
4 Correct 0 ms 3044 KB Output is correct
5 Correct 0 ms 3044 KB Output is correct
6 Correct 0 ms 3044 KB Output is correct
7 Correct 0 ms 3044 KB Output is correct
8 Correct 0 ms 3044 KB Output is correct
9 Correct 0 ms 3044 KB Output is correct
10 Correct 0 ms 3044 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3044 KB Output is correct
2 Correct 0 ms 3044 KB Output is correct
3 Correct 0 ms 3044 KB Output is correct
4 Correct 0 ms 3044 KB Output is correct
5 Correct 0 ms 3044 KB Output is correct
6 Correct 0 ms 3044 KB Output is correct
7 Correct 0 ms 3044 KB Output is correct
8 Correct 0 ms 3044 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3044 KB Output is correct
2 Correct 0 ms 3044 KB Output is correct
3 Correct 4 ms 3044 KB Output is correct
4 Correct 0 ms 3044 KB Output is correct
5 Correct 4 ms 3044 KB Output is correct
6 Correct 0 ms 3044 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3044 KB Output is correct
2 Correct 32 ms 3044 KB Output is correct
3 Correct 40 ms 3044 KB Output is correct
4 Correct 24 ms 3044 KB Output is correct
5 Correct 32 ms 3044 KB Output is correct
6 Correct 32 ms 3044 KB Output is correct