Submission #4948

#	Time	Username	Problem	Language	Result	Execution time	Memory
4948		hana5505	전봇대 (KOI13_pole)	C++98	100 / 100	52 ms	3044 KiB

pole

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