记录编号	464993	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	Hyoi_0Koto	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-10-26 17:15:13	内存使用	0.00 MiB

/*written by 0koto*/
#p\
ragma GCC optimize("Ofast")
#include"cstdio"
#include"cctype"
#include"iostream"
#include"algorithm"
#define loop(i,j,k) for(register int i=j;i<=k;++i)
using namespace std;
inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(!(c^'-'))f=-1;c=getchar();}
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=f;
}
inline int out(int x){
    if(!x) return putchar('0'),0;
    if(x<0) putchar('-'),x=-x;
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int inf=0x7effffff;
const int maxl=100001; 
int l,s,t,m,n,a[101],b[101],f[maxl],p[maxl],ans=inf;
inline void dp(){
	fill(f+1,f+l+1,inf);f[0]=0;
	loop(i,0,l)loop(j,s,t)if(i+j<l){
		if(p[i+j]) f[i+j]=min(f[i+j],f[i]+1);else f[i+j]=min(f[i+j],f[i]);
	}
	loop(i,l-t,l) ans=min(ans,f[i]);
}
inline int koto(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	in(l),in(s),in(t),in(m);
	if(!(s^t)){
		ans=0;
		loop(i,1,m){
			in(n);
			if(!(n%s)) ans++;
		}
	}else{
		loop(i,1,m) in(a[i]);
		sort(a+1,a+m+1);
		loop(i,1,m){
			if(a[i]-a[i-1]>t) b[i]=t;else b[i]=a[i]-a[i-1];
		}
		loop(i,1,m) a[i]=a[i-1]+b[i],p[a[i]]=1;l=a[m];
		dp();
	}
	out(ans);
}
int zero=koto();
int main(){;}