e7KsGQ - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define nmax (long long)(1e6+7)
#define oo (long long)(1e18)
#define INF (int)(1e9+7)
#define fi first
#define se second
#define pii pair<int, int>
#define Hung ""
using namespace std;


ll m, n , x, y, t;
ll dx[] = {-1, 0, 1, 0};
ll dy[] = {0, 1, 0, -1};
struct diem{
    ll ui, uj, vi, vj;
    ll sum;
    ll su, sv;
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(Hung".inp", "r")){
        freopen(Hung".inp", "r", stdin);
        freopen(Hung".out", "w", stdout);
    }
    cin >> m >> n >> x >> y >> t;
    vector<vector<ll>> a(m + 2, vector<ll>(n + 2, 0));
    for (ll i = 1; i <= m; i++)
        for (ll j = 1; j <= n; j++)
            cin >> a[i][j];

    if (m == 1 && n == 1){
        ll res = (t + 1) / 2;
        cout << res * a[1][1];
        return 0;
    }
    vector<diem> Edges;
    for(ll i = 1; i <= m; i++){
        for(ll j = 1; j <= n; j++){
            for(ll d = 0; d < 4; d++){
                ll ni = i + dx[d];
                ll nj = j + dy[d];
                if (ni >= 1 && ni <= m && nj >= 1 && nj <= n){
                    if (i < ni || (i == ni && j < nj)){
                        Edges.push_back({i, j, ni, nj, a[i][j] + a[ni][nj], a[i][j], a[ni][nj]});
                    }
                }
            }
        }
    }
    ll D = min(t, m + n + 2);

    vector<vector<ll>> dp0(m + 2, vector<ll>(n + 2, -oo)), dp1(m + 2, vector<ll>(n + 2, -oo));
    dp0[x][y] = 0;

    for(ll k = 1; k <= D; k++){
        for(ll i = 1; i <= m; i++)
            for(ll j = 1; j <= n; j++)
                dp1[i][j] = -oo;
        for(ll i = 1; i <= m; i++){
            for(ll j = 1; j <= n; j++){
                ll tmp = dp0[i][j];
                if (tmp == -oo) continue;
                for(ll d = 0; d < 4; d++){
                    ll ni = i + dx[d];
                    ll nj = j + dy[d];
                    if (ni < 1 || ni > m || nj < 1 || nj > n) continue;
                    ll nv = tmp + a[ni][nj];
                    if (nv > dp1[ni][nj])
                        dp1[ni][nj] = nv;
                }
            }
        }
        dp0.swap(dp1);
    }
    if (t <= D) {
        ll res = 0;
        for(ll i = 1; i <= m; i++)
            for(ll j = 1; j <= n; j++)
                res = max(res, dp0[i][j]);
        cout << res;
        return 0;
    }
    ll k = (t - D) / 2;
    ll r = (t - D) % 2;
    ll res = 0;
    for(diem x : Edges){
        ll fu = dp0[x.ui][x.uj];
        ll fv = dp0[x.vi][x.vj];
        if (fu > -oo){
            ll cand = fu + k * x.sum + (r ? x.sv : 0);
            res = max(res, cand);
        }
        if (fv > -oo){
            ll cand = fv + k * x.sum + (r ? x.su : 0);
            res = max(res, cand);
        }
    }
    cout << res;
    return 0;
}