/** 正難則反* f[i] 表示前 i 個數中被刪除的數的最小和* f[i] = min(f[j]) + num, i - k + 1 <= j < i;* 單調隊列維護 */ #include <bits/stdc++.h>#define LL long longconst int N = 1e5 + 10;LL tot, d, n, k; LL p[N], head = 1, tail = 1; LL q[N], f[N], ans;int main() {std:: cin >> n >> k; for(int i = 1; i <= n; ++ i){std:: cin >> d;tot += d;f[i] = q[head] + 1LL * d;while(head <= tail && q[tail] >= f[i]) tail --;q[++ tail] = f[i], p[tail] = i;while(head <= tail && p[head] < i - k) head ++;}for(int i = n - k; i <= n; ++ i) ans = std:: max(ans, 1LL * tot - 1LL * f[i]);printf("%lld", ans); }
?
