CUBE-119: COI Road Cube

#include <bits/stdc++.h>

using namespace std;
struct Data{
    int val;
    int idx;
};
const int N = 1e2 + 10;
const int M = 1e4 + 10;
int dp[N][M], ar[N][M];

int main(){

    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);

    for(int j = 1; j <= m; j++){
        scanf("%d", &ar[1][j]);
        dp[1][j] = ar[1][j];
    }

    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= m; j++) {
            scanf("%d", &ar[i][j]);
        }
        deque <Data> dq;

        for(int j = 1; j <= min(k + 1, m); j++){
            while(!dq.empty() and dq.back().val <= dp[i-1][j])
                dq.pop_back();
            dq.push_back({dp[i-1][j], j});
        }
        dp[i][1] = dq.front().val + ar[i][1];

        for(int j = 2; j <= m; j++){
            while(!dq.empty() and j - dq.front().idx > k)
                dq.pop_front();
            while(j + k <= m and !dq.empty() and dq.back().val <= dp[i-1][j+k])
                dq.pop_back();
            dq.push_back({dp[i-1][j+k], j + k});
            dp[i][j] = dq.front().val + ar[i][j];
        }
    }

    int mx = 0;
    for(int j = 1;j <= m; j++)
        mx = max(mx, dp[n][j]);
    printf("%d", mx);

    return 0;
}