oj.uz

Submission #17661

# Submission time Handle Problem Language Result Execution time Memory
17661 2016-01-08T00:17:13 Z Namnamseo 점 모으기 (KOI13_collect) C++14
24 / 24
 41 ms 1864 KB 
#include <cstdio>

int n,m;

int x[100010];
int y[100010];

int abs(int x){ return x>0?x:-x; }

long long sum(int *axis, int pos){
    int i;
    long long ret=0;
    for(i=0;i<m;++i) ret+=abs(axis[i]-pos);
    return ret;
}

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

long long find(int *axis){
    int l=1, a=min(2,n), b=min(3,n), r=n;
    while(l+3<r){
        a=(l*2+r)/3;
        b=(l+r*2)/3;
        if(sum(axis,a)>sum(axis,b)) l=a;
        else r=b;
    }
    a=(l*2+r)/3;
    b=(l+r*2)/3;
    return min(min(sum(axis,l), sum(axis,a)), min(sum(axis,b), sum(axis,r)));
}

int main()
{
    scanf("%d%d",&n,&m);
    int i;
    for(i=0;i<m;i++) scanf("%d%d",x+i,y+i);
    printf("%lld\n",find(x)+find(y));
    return 0;
}

Subtask #1
2.4 / 2.4

# 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

Subtask #2
2.4 / 2.4

# 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

Subtask #3
2.4 / 2.4

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

Subtask #4
3.36 / 3.36

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1864 KB Output is correct
2 Correct 17 ms 1864 KB Output is correct
3 Correct 13 ms 1864 KB Output is correct

Subtask #5
3.36 / 3.36

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1864 KB Output is correct
2 Correct 24 ms 1864 KB Output is correct
3 Correct 29 ms 1864 KB Output is correct

Subtask #6
3.36 / 3.36

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1864 KB Output is correct
2 Correct 28 ms 1864 KB Output is correct
3 Correct 24 ms 1864 KB Output is correct

Subtask #7
3.36 / 3.36

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1864 KB Output is correct
2 Correct 28 ms 1864 KB Output is correct
3 Correct 39 ms 1864 KB Output is correct

Subtask #8
3.36 / 3.36

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1864 KB Output is correct
2 Correct 37 ms 1864 KB Output is correct
3 Correct 41 ms 1864 KB Output is correct