codeforce#933 题解

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index = end; index --)
 
using namespace std;
 
typedef long long ll;
const int maxn = 2e5+5;
struct contianer {
    private:
        int step;
        int pos = 0;
        ll loop[maxn];
        multiset store;
    public:
        contianer(int step):step(step) {}
        
        void add(ll x) {
            int now = pos % step;
            // need to remove
            if (pos >= step) {
                store.erase(store.find(loop[now]));
            }
            
            loop[now] = x;
            store.insert(x);
            pos ++;
        }
        
        /**
          * get min number
         */
        ll get() {
            return *store.begin();
        }
        
        void setStep(int s);
        
        void clear();
};
void contianer::setStep(int s) {
    step = s;
}
void contianer::clear() {
    store.clear();
    pos = 0;
}
ll sum[128];
int store[maxn];
ll dp[maxn][2];
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        int n,m,k,d;
        cin>>n>>m>>k>>d;
        contianer heap(d);
        
        sum[0] = 0LL;
        // input and dp
        rep(_,0,n) {
            // input
            rep(i,0,m) cin>>store[i];
            // init
            heap.clear();
            heap.add(store[0] + 1);
            dp[0][0] = dp[0][1] = store[0] + 1;
            // dp
            rep(i,1,m-1) {
                ll min_cost = heap.get();
                dp[i][0] = min_cost;
                dp[i][1] = min(dp[i-1][0], min_cost) + store[i] + 1;
//                cout
            ans = min(ans, sum[i] - sum[i-k]);
        }
        // cout
        cout
    int val;
    int ind;
};
int store[maxn/2];
record dif[maxn/2];
int d[maxn], f[maxn];
bool cmp(const record& a, const record& b) {
    return a.val