oj.uz

Submission #61739

# Submission time Handle Problem Language Result Execution time Memory
61739 2018-07-26T13:48:19 Z ansol4328 전봇대 (KOI13_pole) C++
100 / 100
 39 ms 8756 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 828 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 4 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 828 KB Output is correct
2 Correct 2 ms 828 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 3 ms 884 KB Output is correct
6 Correct 3 ms 892 KB Output is correct
7 Correct 3 ms 916 KB Output is correct
8 Correct 4 ms 924 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1076 KB Output is correct
2 Correct 5 ms 1076 KB Output is correct
3 Correct 7 ms 1296 KB Output is correct
4 Correct 8 ms 1408 KB Output is correct
5 Correct 8 ms 1496 KB Output is correct
6 Correct 6 ms 1592 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4240 KB Output is correct
2 Correct 36 ms 5072 KB Output is correct
3 Correct 34 ms 6072 KB Output is correct
4 Correct 39 ms 7176 KB Output is correct
5 Correct 31 ms 7924 KB Output is correct
6 Correct 35 ms 8756 KB Output is correct