Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

/**********************************************************************************/
/*  Problem: a605 "交錯和" from 原創問題，如有雷同，純屬巧合     */
/*  Language: CPP (1755 Bytes)                                                    */
/*  Result: AC(152ms, 2.7MB) judge by this@ZeroJudge                              */
/*  Author: morris1028 at 2013-02-22 20:56:34                                     */
/**********************************************************************************/


#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
struct E {
    long long v;
    int i;
};
struct cmp {
    bool operator() (E a, E b) {
        return a.v < b.v;
    }
};
int main() {
    int i, n, m;
    while(scanf("%d %d", &n, &m) == 2) {
        priority_queue<E, vector<E>, cmp> Q1, Q2; // plus, minus
        long long ans = -(1LL<<60), Ai;
        E a, b, c, d;
        for(i = 0; i < n; i++) {
            scanf("%lld", &Ai);
            if(Ai > ans)  ans = Ai;
            c.i = d.i = -1;
            while(!Q1.empty()) {
                a = Q1.top();
                if(a.i < i-m) {
                    Q1.pop();
                    continue;
                }
                b.v = a.v - Ai, b.i = i;
                if(b.v > ans)   ans = b.v;
                c = b;
                break;
            }
            while(!Q2.empty()) {
                a = Q2.top();
                if(a.i < i-m) {
                    Q2.pop();
                    continue;
                }
                b.v = a.v + Ai, b.i = i;
                if(b.v > ans)   ans = b.v;
                d = b;
                break;
            }
            a.v = Ai, a.i = i;
            if(c.i != -1) {
                while(!Q2.empty() && c.v > Q2.top().v)
                    Q2.pop();
                Q2.push(c);
            }
            if(d.i != -1) {
                while(!Q1.empty() && (d.v > Q1.top().v || a.v > Q1.top().v))
                    Q1.pop();
                if(d.v > a.v)
                    Q1.push(d);
                else
                    Q1.push(a);
            } else    Q1.push(a);
        }
        printf("%lld\n", ans);
    }
    return 0;
}