数据太水了,这个代码也能过???????
  • 板块P1714 切蛋糕
  • 楼主Man_CCNU
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/11 20:08
  • 上次更新2023/10/24 04:42:10
查看原帖
数据太水了,这个代码也能过???????
524191
Man_CCNU楼主2023/1/11 20:08
#include<iostream>
#include<deque>

using namespace std;

const int N = 5e5 + 10;

int a[N], b[N], n, m, res = -1e8;
deque<int>que;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        while (que.size() && i - m > que.front()) que.pop_front();
        if (que.size()) {
            res = max(res, b[i] - b[que.front()]);
        }
        else res = max(res, b[i]);
        while (que.size() && b[i] <= b[que.back()]) que.pop_back();
        que.push_back(i);
    }
    cout << res << endl;

    return 0;
}

数据:5 3 1 2 3 -2 -2

2023/1/11 20:08
加载中...