CUBE-T119: COI Road Cube

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using pii = pair<int, int>;

int main(){

    int row, col, lim;
    scanf("%d", &row);
    scanf("%d", &col);
    scanf("%d", &lim);

    vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
    for(int i = 1; i <= row; ++i){
        deque<pii> q;
        for(int j = 1; j <= lim; ++j){
            if(j <= col){
                while(!q.empty() && q.back().first <= dp[i - 1][j]){
                    q.pop_back();
                }
                q.push_back(make_pair(dp[i - 1][j], j));
            }
        }
        for(int j = 1; j <= col; ++j){
            int x;
            scanf("%d", &x);
            if(j + lim <= col){
                while(!q.empty() && q.back().first <= dp[i - 1][j + lim]){
                    q.pop_back();
                }
                q.push_back(make_pair(dp[i - 1][j + lim], j + lim));
            }
            while(!q.empty() && q.front().second < j - lim){
                q.pop_front();
            }
            dp[i][j] = x + q.front().first;
        }
    }

    int mx = 0;
    for(int i = 1; i <= col; ++i){
        mx = max(mx, dp[row][i]);
    }

    cout << mx;

    return 0;
}