大佬们看看 wa了后面两个hack数据
查看原帖
大佬们看看 wa了后面两个hack数据
1106289
KomorKomor楼主2024/5/3 20:26
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define ll long long 
using namespace std;

ll n,l,r,ans=-1e9,head,tail;
ll a[400010];
ll q[400010];
ll dp[400010];
//dp[i]的含义是走到第i个格子时候获得的最大冰冻指数
vector<int> v;

void solve()
{
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++)
    {
        cin>>a[i];
        if(i>=l)    dp[i]=a[i];
    }
    //维护i+l,i+r区间最大dp值的单调队列
    for(int i=l;i<=n;i+=1)
    {
        while(head<=tail&&dp[q[tail]]<=dp[i]) tail--;
        q[++tail]=i;
        while(head<=tail&&i+r-l+1<=i) head++;
        dp[i+l]=dp[q[head]]+a[i+l];
    }

    for(int i=l;i<=2*n;i++)   ans=max(ans,dp[i]);
    cout<<ans<<endl;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--)   solve();
    return 0;
}

2024/5/3 20:26
加载中...