TLE*4

Kiritan @ 2019-11-10 20:05:34

#include<cstdio>
#include<algorithm>
const int maxn=4000005;
long long n,l,r,f[maxn],dp[maxn],maxm;
bool s[maxn];
int main(){
    scanf("%lld%lld%lld",&n,&l,&r);
    for(int i(0),j(0);i<=n;i+=l,j+=r)
        for(int k(i);k<=j;k++)s[k]=1;
    for(int i(0);i<=n+r;i++){
        if(i<=n)scanf("%lld",&f[i]);
        dp[i]=f[i];
        if(i>=l){
            for(int j(i-r);j<=i-l;j++)
            if(s[i]==1&&s[j]==1)f[i]=std::max(f[i],dp[i]+f[j]);
        dp[i]=f[i];
        maxm=std::max(maxm,dp[i]);
        }
    }
        printf("%lld",maxm);
}

by Smile_Cindy @ 2019-11-10 20:07:07

@Kiritan

您以为您是wys吗？

by Kiritan @ 2019-11-10 20:28:25

@Alpha 求优化

by Kiritan @ 2019-11-10 21:06:40

#pragma GCC optimize(3,"Ofast","inline")
#include<cstdio>
#include<algorithm>
const int maxn=400005;
long long n,l,r,f[maxn],dp[maxn],maxm;
bool s[maxn];
int main(){
    scanf("%lld%lld%lld",&n,&l,&r);
    for(int i(0),j(0);j<=n+r;i+=l,j+=r)
        for(int k(i);k<j;k++)s[k]=1;
    for(int i(0);i<=n+r;i++){
        if(i<=n)scanf("%lld",&f[i]);
        dp[i]=f[i];
        if(i>=l){
            for(int j(i-r);j<=i-l;j++)
                if(s[i]==1&&s[j]==1)f[i]=std::max(f[i],dp[i]+f[j]);
            dp[i]=f[i];
            if(s[i]==1)maxm=std::max(maxm,dp[i]);
        }
    }
        printf("%lld",maxm);
}

AC了 被迫o3....

by NotFound_404 @ 2020-01-21 15:30:43

可以自己手动开臭氧的？？？

by NotFound_404 @ 2020-01-21 15:30:53

@Kiritan

by Kiritan @ 2020-02-17 21:24:33

@NotFound_404 手动