Pagini recente » Cod sursa (job #2514536) | Cod sursa (job #235223) | Cod sursa (job #1355672) | Cod sursa (job #1137115) | Cod sursa (job #635636)
Cod sursa(job #635636)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 1000010
int A[MAXN],DP[MAXN];
int i,st;
int D,N,K;
char s[2*MAXN];
/*int cbin(int st, int L) {
int dr,m,rez;
dr=L; rez=L;
m=(st+dr)/2;
while(st<=dr) {
if(A[L]-A[m]+1<=D) {
rez=min(rez,m);
dr=m-1;
}
else
st=m+1;
m=(st+dr)/2;
}
return rez;
}*/
int main() {
freopen("zombie.in","r",stdin);
freopen("zombie.out","w",stdout);
scanf("%d %d %d\n",&D,&N,&K);
//for(i=1;i<=N;i++)
// scanf("%d",&A[i]);
fgets(s,sizeof(s),stdin);
int cnt=0;
for(i=0;i<=(int)sizeof(s);i++) {
if(s[i]=='\0' || s[i]=='\n') break;
while(s[i]==' ') i++;
if(s[i]=='\0' || s[i]=='\n') break;
cnt++;
A[cnt]=0;
for(;s[i]>='0' && s[i]<='9';i++)
A[cnt]=10*A[cnt]+(s[i]-'0');
}
if(cnt!=N) for(;;);
st=1; DP[1]=1;
for(i=2;i<=N;i++) {
//st=cbin(st,i);
while(A[i]-A[st]+1>D)
st++;
DP[i]=min(DP[i-1]+1,DP[st-1]+K);
}
printf("%d",DP[N]);
}