这道题评测有BUG？还是洛谷评测机和我不太一样

CC_dsm @ 2019-11-03 08:23:57

#include <queue>
#include <iostream>

using namespace std;

#define MAXN 200001

deque<int> que;
int n, l, r, a[MAXN], dp[MAXN];

void initialize(void);

int main(void)
{
    ios::sync_with_stdio(false);
    int ans = 0;
    initialize();
    /*for (int i = 0; i <= r - l; i++)
    {
        cout << "dp[" << i << "] is " << dp[i] << endl;
    }*/
    for (int i = r; i <= n; i++)
    {
        dp[i] = dp[que.front()] + a[i];
        //cout << "dp[" << i << "] is from dp[" << que.front() << "], so its val is " << dp[i] << endl;
        if (que.front() <= i - r)
            que.pop_front();
        while (!que.empty() && dp[i - l + 1] > dp[que.back()])
            que.pop_back();
        que.emplace_back(i - l + 1);
    }
    for (int i = n - r + 1; i <= n; i++)
        ans = max(ans, dp[i]);
    cout << ans;
    //system("pause");
    return 0;
}

void initialize(void)
{
    int max_ = 0;
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++)
        cin >> a[i];
    que.emplace_back(0);
    for (int i = l; i < 2 * l; i++)
    {
        if (i > r - l)
            return;
        dp[i] = a[i];
        while (!que.empty() && dp[i] > dp[que.back()])
            que.pop_back();
        que.emplace_back(dp[i]);
    }
    for (int i = 2 * l; i <= r - l; i++)
    {
        max_ = max(max_, dp[i - l]);
        dp[i] = max_ + a[i];
        while (!que.empty() && dp[i] > dp[que.back()])
            que.pop_back();
        que.emplace_back(dp[i]);
    }
    for (int i = r - l + 1; i < r; i++)
    {
        max_ = max(max_, dp[i - l]);
        dp[i] = max_ + a[i];
    }
}

by CC_dsm @ 2019-11-03 08:26:48

？？？？我交了个题解，题解A了，然而我和题解的输出没有不同啊？

by rui_er @ 2019-11-03 08:35:25

bug:哪来这么多kkk

by tZEROちゃん @ 2019-11-03 08:36:07

kkk:哪来这么多bug

by fa_555 @ 2019-11-03 08:39:39

评测机是 linux 下的，关你 win 下什么事（

在线 IDE，请

by CC_dsm @ 2019-11-03 08:48:57

@fa_555 20k的数据量，在线IDE说输入长度不合法。。。

by 与世无争 @ 2019-11-05 00:08:27

我也是，自测过了，在洛谷评测机上过不掉

#pragma GCC optimize(2)
#include<cstdio>
inline int read() {
    int n=0,w=1;
    register char c=getchar();
    while (c<'0'||c>'9') {
        if (c=='-') w=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return n*w;
}
int max(int q,int p) {
    return (q>p)?q:p;
}
const int N=2000005;
int n,l,r,a[N],q[N][2],head,tail,f[N],ans=-1e9;
int main() {
    n=read();
    l=read();
    r=read();
    for (int i=0; i<=n; i++) a[i]=read();
    for (int i=1; i<l; i++) f[i]=-1e9;
    for (int i=l; i<=r; i++) {
        f[i]=-1e9;
        for (int j=i-l; j>=i-r; j--) f[i]=max(f[i],f[j]);
        f[i]+=a[i];
    }
    for (int i=l; i<=r+1-l; i++) {
        while (head<tail&&q[tail][0]<f[i]) tail--;
        q[++tail][0]=f[i];
        q[tail][1]=i;
    }
    for (int i=r+1; i<=n; i++) {
        while (head<tail&&i-q[head+1][1]>r) head++;
        f[i]=a[i]+q[head+1][0];
        int k=i+1-l;
        while (head<tail&&(q[tail][0]<f[k]||i-q[tail][1]>r)) tail--;
        q[++tail][0]=f[k];
        q[tail][1]=k;
    }
    for (int i=n-r+1; i<=n; i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}
//By与世无争

by CC_dsm @ 2019-11-05 07:14:01

@与世无争 为此我还搭了个虚拟机，。。。

by 程义轩 @ 2020-10-24 11:46:07

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int f[200005];
int q[200005], head = 1, tail;
int n, l, r;
int main() {
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    memset(f, 0xcf, sizeof(f));
    int ans = f[0];
    f[0] = 0;
    int j = 0;
    for (int i = l; i <= n; i++) {
        while (head <= tail && f[q[tail]] < f[j]) 
            tail--;
         q[++tail] = j;
        if (q[tail] - q[head] > r - l) 
            head++;
        f[i] = f[q[head]] + a[i];
        j++;
    }
    for (int i = n - r + 1; i <= n; i++) {
        ans = max(ans, f[i]);
    }

    cout << ans << endl;
    return 0;
}