比赛 2025.3.18 评测结果 AAAAAAAAAA
题目名称 琪露诺 最终得分 100
用户昵称 wdsjl 运行时间 0.152 s
代码语言 C++ 内存使用 7.92 MiB
提交时间 2025-03-18 20:06:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
void read(int& now) {
    char word = getchar();
    bool is_negative = false;
    now = 0;
    while (word < '0' || word > '9') {
        if (word == '-') {
            is_negative = true;
        }
        word = getchar();
    }
    while (word >= '0' && word <= '9') {
        now = now * 10 + (word - '0');
        word = getchar();
    }
    if (is_negative) {
        now = -now;
    }
}

const int INF = 1e9;

int N, L, R;
int ans = -INF;
int pos;
const int MN = 1000001;
int dp[MN];
int Queue[MN];
int Head = 1, Tail = 0;
int value[MN];
int pre[MN];

void pr(int now) {
    if (pre[now] != -1) {
        pr(pre[now]);
    }
    printf("%d ", now);
}
int main() {
    freopen("iceroad.in", "r", stdin);
    freopen("iceroad.out", "w", stdout);
    read(N);
    read(L);
    read(R);
    for (int i = 0; i <= N; ++i) {
        read(value[i]);
    }
    memset(pre, -1, sizeof(pre));
    for (int i = L; i <= N; ++i) {
        int res;
        if (i - L <= 0) {
            continue;
        }
        res = dp[i - L];
        while (Head <= Tail && (Queue[Head] + L > i || Queue[Head] + R < i || Queue[Head] > i)) {
            ++Head;
        }
        while (Head <= Tail && res > dp[Queue[Tail]]) {
            --Tail;
        }
        Queue[++Tail] = i - L;
        pre[i] = Queue[Head];
        dp[i] = value[i] + dp[Queue[Head]];
        if (ans < dp[i]) {
            ans = dp[i];
            pos = i;
        }
    }
    printf("%d\n", ans);
    pr(pos);
    printf("-1");
    return 0;
}