182C - Optimal Sum - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define st first
#define nd second
 
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const int N = 1e5 + 5;
 
int n, len, k, a[N];
 
ll calc(){
ordered_set s;
ll at = 0, ans = 0;
for(int i = 1; i <= n; i++){
at += a[i];
if(a[i] < 0){
s.insert({a[i], i});
if(s.order_of_key({a[i], i}) < k){
at -= 2 * a[i];
if(s.size() > k)
at += 2 * (s.find_by_order(k)->st);
}
}
if(i >= len){
ans = max(ans, at);
at -= a[i - len + 1];
if(a[i - len + 1] < 0){
s.erase({a[i - len + 1], i - len + 1});
if(s.order_of_key({a[i - len + 1], i - len + 1}) < k){
at += 2 * a[i - len + 1];
if(s.size() >= k)
at -= 2 * (s.find_by_order(k - 1)->st);
}
}
}
}
return ans;
}
 
int main(){
scanf("%d %d", &n, &len);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &k);
ll ans = calc();
for(int i = 1; i <= n; i++)
a[i] *= -1;
printf("%lld\n", max(ans, calc()));
return 0;
}