Подводная лодка

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2500;
int decode[278];
string b[2500];
int a[N][N];

int top_max[N][N];
int bot_max[N][N];

int _end[N][N]; // считаем только с концовкой
int _begin[N][N]; // считаем только с началом
int sht[N][N];

signed main()
{
#ifndef arrias
    freopen("submarine.in", "r", stdin);
    freopen("submarine.out", "w", stdout);
#endif
    int k;
    cin >> k;
    for (char c = 'a'; c < 'a' + k; ++c) {
        int t;
        cin >> t;
        decode[c] = t;
    }
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
        cin >> b[i];
        for (int j = 0; j < w; ++j) {
            a[i][j] = decode[b[i][j]];
        }
    }
    for (int j = 0; j < w; ++j) {
        vector <int> pref(h);
        pref[0] = a[0][j];
        for (int i = 1; i < h; ++i)
            pref[i] = pref[i - 1] + a[i][j];
        int pref_min = 0;
        for (int i = 0; i < h; ++i) {
            top_max[i][j] = pref[i] - pref_min;
            pref_min = min(pref_min, pref[i]);
        }
        pref[h - 1] = a[h - 1][j];
        for (int i = h - 2; i > -1; --i) {
            pref[i] = pref[i + 1] + a[i][j];
        }
        pref_min = 0;
        for (int i = h - 1; i > -1; --i) {
            bot_max[i][j] = pref[i] - pref_min;
            pref_min = min(pref_min, pref[i]);
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            bot_max[i][j] -= a[i][j];
            top_max[i][j] -= a[i][j];
            sht[i][j] = top_max[i][j] + bot_max[i][j];
        }
    }
    for (int i = 0; i < h; ++i) {
        // считаем end
        vector <int> pref(w);
        pref[w - 1] = a[i][w - 1];
        for (int j = w - 2; j > -1; --j)
            pref[j] = pref[j + 1] + a[i][j];
        _end[i][w - 1] = a[i][w - 1] + sht[i][w - 1];
        int pref_min = min(0ll, pref[w - 1]);
        for (int j = w - 2; j > -1; --j) {
            _end[i][j] = max(_end[i][j + 1] + a[i][j], pref[j] - pref_min + sht[i][j]);
            pref_min = min(pref_min, pref[j]);
        }
        // считаем begin
        pref.assign(w, 0);
        pref[0] = a[i][0];
        for (int j = 1; j < w; ++j) {
            pref[j] = pref[j - 1] + a[i][j];
        }
        _begin[i][0] = a[i][0] + top_max[i][0];
        pref_min = min(0ll, pref[0]);
        for (int j = 1; j < w; ++j) {
            _begin[i][j] = max(_begin[i][j - 1] + a[i][j], pref[j] - pref_min + top_max[i][j]);
            pref_min = min(pref_min, pref[j]);
        }
    }
    int ans = -1e18;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j + 1 < w; ++j) {
            ans = max(ans, _begin[i][j] + _end[i][j + 1]);
        }
    }
    cout << ans;
    return 0;
}