阅读

Solution

20分

\(f[i]=max\{f[j]-\lceil\frac{t[i]-t[j]}{D}\rceil\times{A}\}+b[i]\).

50分

对于\(D\leq100\),对于每个\(t_i\;mod\;D\)同余的贪心.枚举\(mod\;D\)不同的值即可.

100分

可以发现，
当\(t[j]时,\(\lceil\frac{t[i]-t[j]}{D}\rceil=\lfloor\frac{t[i]}{D}\rfloor-\lfloor\frac{t[j]}{D}\rfloor+1\);
当\(t[j]\geq{t[i]}\)时,\(\lceil\frac{t[i]-t[j]}{D}\rceil=\lfloor\frac{t[i]}{D}\rfloor-\lfloor\frac{t[j]}{D}\rfloor\);
\(f[i]-\lfloor\frac{m}{D}\rfloor-\lfloor\frac{k}{D}\rfloor=max\{max\{f[1...j-1]\}-a,max\{f[j...m]\}\}\)
(\(j\)表示\(mod\;D\)的值离散后的位置,离散后共有m个值).
最后全部加上\(\lfloor\frac{m}{D}\rfloor-\lfloor\frac{k}{D}\rfloor\)就好啦.
P.S.写代码的时候比较傻,所以写得正确性和简洁性堪忧.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
#define M 300005
using namespace std;
typedef long long ll;
ll f[N],g[N],b[N],t[N],a,d,m,k,ans;
int p[N],idp[N],ids[N],n,cnt;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
//i比j优 
inline bool cmp(int i,int j){
    return f[i]+t[i]/d*a>f[j]+t[j]/d*a;
}
inline int lowbit(int k){
    return k&(-k);
}
inline void change(int k){
    for(int i=k;i<=cnt;i+=lowbit(i))
        if(!idp[i]||cmp(g[k],idp[i])) idp[i]=g[k]; 
    for(int i=cnt-k+1;i<=cnt;i+=lowbit(i)){
        if(!ids[i]||cmp(g[k],ids[i])) ids[i]=g[k];
    }
}
inline int pre(int k){
    int ret=0;
    for(int i=k;i;i-=lowbit(i))
        if(!ret) ret=idp[i];
        else if(cmp(idp[i],ret))
            ret=idp[i];
    return ret;
}
inline int suf(int k){
    int ret=0;
    for(int i=cnt-k+1;i;i-=lowbit(i))
        if(!ret) ret=ids[i];
        else if(cmp(ids[i],ret))
            ret=ids[i];
    return ret;
}
inline void Aireen(){
    scanf("%lld%lld%lld%lld%d",&k,&m,&d,&a,&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&t[i],&b[i]);
    if(n<=1000){
        for(int i=1;i<=n;++i){
            if((t[i]-k)%d) f[i]=-((t[i]-k)/d+1ll)*a+b[i];
            else f[i]=-(t[i]-k)/d*a+b[i];
            for(int j=1;j=0;--k)
                if((t[i]-t[j=g[k]])%d)
                    f[i]=max(f[i],f[j]-((t[i]-t[j])/d+1ll)*a+b[i]);
                else f[i]=max(f[i],f[j]-(t[i]-t[j])/d*a+b[i]);
            if(!g[t[i]%d]) g[t[i]%d]=i;
            else if(cmp(i,g[t[i]%d]))
                g[t[i]%d]=i;
        }
        if((m-k)%d) ans=-((m-k)/d+1ll)*a;
        else ans=-(m-k)/d*a;
        for(int i=1;i<=n;++i)
            if((m-t[i])%d)
                ans=max(ans,f[i]-((m-t[i])/d+1ll)*a);
            else ans=max(ans,f[i]-(m-t[i])/d*a);
        printf("%lld\n",ans);
        return; 
    }
    for(int i=1;i<=n;++i)
        p[i]=(int)(t[i]%d);
    sort(p+1,p+1+n);cnt=1;
    for(int i=2;i<=n;++i)
        if(p[i]!=p[i-1]) p[++cnt]=p[i];
    for(int i=1,j,l;i<=n;++i){
        if((t[i]-k)%d) f[i]=-((t[i]-k)/d+1ll)*a+b[i];
        else f[i]=-(t[i]-k)/d*a+b[i];
        l=lower_bound(p+1,p+1+cnt,(int)(t[i]%d))-p;
        if(l-1){
            j=pre(l-1);
            if(j){
                if((t[i]-t[j])%d) 
                    f[i]=max(f[i],f[j]-((t[i]-t[j])/d+1ll)*a+b[i]);
                else f[i]=max(f[i],f[j]-(t[i]-t[j])/d*a+b[i]);
            }
        }
        j=suf(l);
        if(j){
            if((t[i]-t[j])%d) 
                f[i]=max(f[i],f[j]-((t[i]-t[j])/d+1ll)*a+b[i]);
            else f[i]=max(f[i],f[j]-(t[i]-t[j])/d*a+b[i]);
        }
        if(!g[l]){
            g[l]=i;change(l);
        }
        else if(cmp(i,g[l])){
            g[l]=i;change(l);
        }
    }
    if((m-k)%d) ans=-((m-k)/d+1ll)*a;
    else ans=-(m-k)/d*a;
    for(int i=1;i<=n;++i)
        if((m-t[i])%d)
            ans=max(ans,f[i]-((m-t[i])/d+1ll)*a);
        else ans=max(ans,f[i]-(m-t[i])/d*a);
    printf("%lld\n",ans);
}
int main(){
    freopen("reading.in","r",stdin);
    freopen("reading.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}