Sliding Window Cost

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int n,k; cin>>n>>k;
7  multiset<int> lf,rg;
8  int ls=0,rs=0;
9  auto add=[&](multiset<int>&ms,int&sm,int x){
10    ms.emplace(x);
11    sm+=x;
12  };
13  auto rem=[&](multiset<int>&ms,int&sm,int x){
14    ms.erase(ms.find(x));
15    sm-=x;
16  };
17  auto bal=[&](){
18    while(rg.size()>lf.size()) add(lf,ls,*rg.begin()),rem(rg,rs,*rg.begin());
19    while(lf.size()-rg.size()>1) add(rg,rs,*lf.rbegin()),rem(lf,ls,*lf.rbegin());
20  };
21  int a[n]; for(int i=0,res=0;i<n;++i){
22    cin>>a[i];
23    if(lf.size() && *lf.rbegin()<a[i]) add(rg,rs,a[i]);
24    else add(lf,ls,a[i]);
25    if(i>=k){
26      if(lf.size() && *lf.rbegin()<a[i-k]) rem(rg,rs,a[i-k]);
27      else rem(lf,ls,a[i-k]);
28    }
29    bal();
30    if(i>=k-1){
31      int m=*lf.rbegin();
32      cout<<m*lf.size()-ls+rs-m*rg.size()<<" ";
33    }
34  }
35  cout<<'\n';
36  return 0;
37}