Submission #61739

#	Time	Username	Problem	Language	Result	Execution time	Memory
61739		ansol4328	전봇대 (KOI13_pole)	C++98	100 / 100	39 ms	8756 KiB

pole

#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

struct A
{
    double val;
    int cnt;
};

A m[100002];

int cmp(const A &a, const A &b)
{
    return a.val<b.val;
}

long long min(long long a, long long b) {return a<b ? a : b;}

int n, x[100002];
long long out;

long long sum(long long gap)
{
    long long s=0;
    int i;
    for(i=1 ; i<n ; i++) s+=abs(gap*i-x[i]);
    return s;
}

int main()
{
    int i;
    long long xx, c=0;
    scanf("%d",&n);
    for(i=0 ; i<n ; i++) scanf("%d",&x[i]);
    for(i=1 ; i<n ; i++) m[i].val=(double)x[i]/i, m[i].cnt=i;
    sort(m+1,m+n,cmp);
    xx=(long long)n*(n-1)/2;
    out=sum(m[1].val);
    if(xx%2==1)
    {
        xx=(xx+1)/2;
        i=1;
        while(c<xx) c+=m[i++].cnt;
        i--;
        out=min(out,sum(m[i].val));
        out=min(out,sum(m[i].val+1));
        out=min(out,sum(m[i].val-1));
    }
    else
    {
        i=1;
        xx/=2;
        while(c<xx) c+=m[i++].cnt;
        i--;
        if(c>=xx+1)
        {
            out=min(out,sum(m[i].val));
            out=min(out,sum(m[i].val+1));
            out=min(out,sum(m[i].val-1));
        }
        if(c==xx)
        {
            out=min(out,sum(m[i].val));
            out=min(out,sum(m[i].val+1));
            out=min(out,sum(m[i].val-1));
            out=min(out,sum(m[i+1].val));
            out=min(out,sum(m[i+1].val+1));
            out=min(out,sum(m[i+1].val-1));
        }
    }
    printf("%lld",out);
    return 0;
}

Compilation message (stderr)

pole.cpp: In function 'int main()':
pole.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
pole.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=0 ; i<n ; i++) scanf("%d",&x[i]);
                          ~~~~~^~~~~~~~~~~~

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