제출 #17661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17661		Namnamseo	점 모으기 (KOI13_collect)	C++14	24 / 24	41 ms	1864 KiB

ee

#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
• Subtask 2: 2.4 / 2.4
• Subtask 3: 2.4 / 2.4
• Subtask 4: 3.36 / 3.36
• Subtask 5: 3.36 / 3.36
• Subtask 6: 3.36 / 3.36
• Subtask 7: 3.36 / 3.36
• Subtask 8: 3.36 / 3.36