abc210d WA

// Problem: D - National Railway
// Contest: AtCoder - AtCoder Beginner Contest 210
// URL: https://atcoder.jp/contests/abc210/tasks/abc210_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;

ll h, w, c;
vector<vector<int>> a;
int main(int argc, char **argv)
{
    cin >> h >> w >> c;
    a = vector<vector<int>>(h, vector<int>(w));
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            cin >> a[i][j];

    auto left_mat = vector<vector<ll>>(h, vector<ll>(w));
    auto right_mat = vector<vector<ll>>(h, vector<ll>(w));

    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            left_mat[i][j] = min(j > 0 ? left_mat[i][j - 1] : LLONG_MAX, a[i][j] - c * (i + j)),
            left_mat[i][j] = min(left_mat[i][j], i > 0 ? left_mat[i - 1][j] : LLONG_MAX);
    for (int i = 0; i < h; ++i)
        for (int j = w - 1; j >= 0; --j)
            right_mat[i][j] = min(j < w - 1 ? right_mat[i][j + 1] : LLONG_MAX, a[i][j] - c * (i - j)),
            right_mat[i][j] = min(right_mat[i][j], i > 0 ? right_mat[i - 1][j] : LLONG_MAX);
    ll ans = LLONG_MAX;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j)
            ans = min(ans, a[i][j] + c * (i + j) + (j > 0 ? left_mat[i][j - 1] : left_mat[i][j]));
        for (int j = w - 1; j >= 0; --j)
            ans = min(ans, a[i][j] + c * (i - j) + (j < w - 1 ? right_mat[i][j + 1] : right_mat[i][j]));
    }
    cout << ans << endl;
    return 0;
};