Submission #12136

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

preserve

#include <stdio.h>
#include <algorithm>

int arr[100000];
int sor[100000];

inline bool cmp(const int &a,const int &b)
{
	return a>b;
}

inline int mn(int a,int b)
{
	return a<b?a:b;
}

inline int mx(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int n,k,d,r=0,i;
	scanf("%d%d%d",&n,&k,&d);
	for(i=0;i<k;i++)
		scanf("%d",&arr[i]);
	if(d==1)
	{
		printf("%d",mx(arr[0]-1,n-arr[k-1]));
		return 0;
	}
	if(k==1)
	{
		printf("%d",n-1);
		return 0;
	}
	if(d>=2*k)
	{
		printf("%d",n-k);
		return 0;
	}
	for(i=0;i<k-1;i++)
		sor[i]=arr[i+1]-arr[i]-1;
	std::sort(sor,sor+k-1,cmp);
	if(d%2)
	{
		for(i=0;i<(d-1)/2-1;i++)
			r+=sor[i];
		r+=mx(sor[(d-1)/2-1]+mx(arr[0]-1,n-arr[k-1]),arr[0]-1+n-arr[k-1]);
	}
	else
	{
		for(i=0;i<d/2-1;i++)
			r+=sor[i];
		r+=mx(arr[0]-1+n-arr[k-1],sor[d/2-1]);
	}
	printf("%d",r);
	return 0;
}

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