Submission #12217

#	Time	Username	Problem	Language	Result	Execution time	Memory
12217		paulsohn	격자 보존하기 (GA9_preserve)	C11	100 / 100	40 ms	2452 KiB

preserve

#include<stdio.h>
#include<stdlib.h>

int n, k, d;
int p[100010], Gap[100010], lb, rb, sum, sum2, score;

void mergesort(int* po, int n){
    int *pt, *pt2, *tmp;
    int rm, rm2, h=0, i;

    if(n<2) return;

    pt=po;
    pt2=po+n/2;

    rm=n/2;
    rm2=n-n/2;

    mergesort(pt, rm);
    mergesort(pt2, rm2);

    tmp=(int*) malloc(sizeof(int)*n);

    while(rm && rm2){
        if(*pt>*pt2){
            tmp[h++]=*(pt++);
            rm--;
        }
        else{
            tmp[h++]=*(pt2++);
            rm2--;
        }
    }
    while(rm){
        tmp[h++]=*(pt++);
        rm--;
    }
    while(rm2){
        tmp[h++]=*(pt2++);
        rm2--;
    }
    for(i=0; i<n; i++){
        po[i]=tmp[i];
    }
    free(tmp);
    return;
}

int main(){
    int i, tmp;
    scanf("%d %d %d", &n, &k, &d);
    for(i=0;i<k;i++){
        scanf("%d", &p[i]);
        if(i) Gap[i-1]=p[i]-p[i-1]-1;
    }
    lb=p[0]-1;
    rb=n-p[k-1];
    mergesort(Gap, k-1);

    for(i=0; i<k-1 && i<d/2-1; i++){
        sum+=Gap[i];
    }
    sum2=sum+(k-1<=d/2-1 ? 0 : Gap[d/2-1]);

    tmp=sum2;
    if(score<tmp) score=tmp;
    tmp=(lb>rb?lb:rb)+(d%2?sum2:sum);
    if(score<tmp) score=tmp;
    tmp=lb+rb+sum;
    if(score<tmp) score=tmp;
    printf("%d\n", score);

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35