为什么后一份代码更快

#include<iostream>
#include<cstdio>
using namespace std;
long long n,w,s,q[5505],pos[5505];
long long a[5505],dp[5505][5505];
int main(){
    scanf("%lld%lld%lld",&n,&w,&s);
    for(long long i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    for(long long i=0;i<=n;++i)	
    for(long long j=0;j<=w;++j)	
    dp[j][i]=-1008600110086001;
    dp[0][0]=0;
    for(long long i=1;i<=n;++i)
	{
		int l=1,r=1;
		q[l]=dp[w][i-1];
		pos[l]=w;
		for(long long j=w;j;--j)
		{
			while(pos[l]>j+s-1 && l<=r)	++l;
			while(q[r]<dp[j-1][i-1] && l<=r)--r;
			pos[++r]=j-1;
			q[r]=dp[j-1][i-1];
			dp[j][i]=q[l]+j*a[i];
		}
	}
    long long ans=-1008600110086001;
    for(long long i=1;i<=w;i++)
    ans=max(dp[i][n],ans);
    printf("%lld\n",ans);
    return 0;
}

更快的:

#include<iostream>
#include<cstdio>
using namespace std;
long long n,w,s,q[5505],pos[5505];
long long a[5505],dp[5505][5505];
int main(){
    scanf("%lld%lld%lld",&n,&w,&s);
    for(long long i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    for(long long i=0;i<=n;++i)	
    for(long long j=0;j<=w;++j)	
    dp[i][j]=-1008600110086001;
    dp[0][0]=0;
    for(long long i=1;i<=n;++i)
	{
		int l=1,r=1;
		q[l]=dp[i-1][w];
		pos[l]=w;
		for(long long j=w;j;--j)
		{
			while(pos[l]>j+s-1 && l<=r)	++l;
			while(q[r]<dp[i-1][j-1] && l<=r)	--r;
			pos[++r]=j-1;
			q[r]=dp[i-1][j-1];
			dp[i][j]=q[l]+j*a[i];
		}
	}
    long long ans=-1008600110086001;
    for(long long i=1;i<=w;i++)
    ans=max(dp[n][i],ans);
    printf("%lld\n",ans);
    return 0;
}

求解答