Submission #12647

#	Time	Username	Problem	Language	Result	Execution time	Memory
12647		dohyun0324	격자 보존하기 (GA9_preserve)	C++98	100 / 100	28 ms	1868 KiB

preserve

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,k,d,ans,a[100010],b[100010],cnt,dap;
int main()
{
    int i;
    scanf("%d %d %d",&n,&k,&d);
    for(i=1;i<=k;i++) scanf("%d",&a[i]);
    //처음,끝 사용 X
    for(i=1;i<k;i++) b[i]=a[i+1]-a[i]-1;
    sort(b+1,b+k);
    for(i=k-1;i>=1;i--)
    {
        cnt+=2;
        if(cnt>d) break;
        dap+=b[i];
    }
    if(ans<dap) ans=dap;
    //처음 또는 끝 사용
    cnt=1; dap=max(n-a[k],a[1]-1);
    for(i=k-1;i>=1;i--)
    {
        cnt+=2;
        if(cnt>d) break;
        dap+=b[i];
    }
    if(ans<dap) ans=dap;
    //처음,끝 사용
    if(d>1)
    {
        cnt=2; dap=n-a[k]+a[1]-1;
        for(i=k-1;i>=1;i--)
        {
            cnt+=2;
            if(cnt>d) break;
            dap+=b[i];
        }
        if(ans<dap) ans=dap;
    }
    printf("%d",ans);
    return 0;
}

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