记录编号	208638	评测结果	AAAAAAAAAA
题目名称	2107.[NOIP 2015]跳石头	最终得分	100
用户昵称	Dissolute丶Tokgo	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2015-11-17 19:13:24	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rep2(i,l,r) for(int i=l;i<r;++i)
#define drep(i,r,l) for(int i=r;i>=l;--i)
#define N 50505
int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

void init(){
	freopen("2015stone.in","r",stdin);
	freopen("2015stone.out","w",stdout);
}

int a[N],d[N];
int L,n,m;

bool pd(int x){
	int cnt=0,tot=0;
	rep(i,1,n+1){
		if(a[i]>=x) tot=0;
		else if(tot+a[i]>=x) tot=0;
		else cnt++,tot+=a[i];
	}
	if(cnt>m) return false;
	else return true;
}

int main(){
	init();
	L=read(),n=read(),m=read();
	rep(i,1,n){
		d[i]=read();
		a[i]=d[i]-d[i-1]; 
	}
	a[0]=0,a[n+1]=L-d[n];
	int l=1,r=L,ans,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(pd(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d",ans);
}