Submission by @naan112358

#include <bits/stdc++.h>
using namespace std;

int main(){
    constexpr unsigned long N = 6500;
    unsigned long W, H;
    cin >> W >> H;
    vector<vector<long>> n(W, vector<long>(H));
    for(auto& i : n)for(auto& j : i)cin >> j;

    vector<vector<bitset<N * 2>>> dp(W, vector<bitset<N * 2>>(H));
    dp[0][0][N + n[0][0]] = true;
    for(unsigned long i = 1; i < W; ++i)dp[i][0] = n[i][0] < 0 ? dp[i - 1][0] >> (-n[i][0]) : dp[i - 1][0] << (n[i][0]);
    for(unsigned long i = 1; i < H; ++i)dp[0][i] = n[0][i] < 0 ? dp[0][i - 1] >> (-n[0][i]) : dp[0][i - 1] << (n[0][i]);
    for(unsigned long i = 1; i < W; ++i)for(unsigned long j = 1; j < H; ++j)dp[i][j] = n[i][j] < 0 ? (dp[i - 1][j] | dp[i][j - 1]) >> (-n[i][j]) : (dp[i - 1][j] | dp[i][j - 1]) << n[i][j];

    long ans{numeric_limits<long>::max()};
    auto k = dp.back().back();
    for(unsigned long i = 0; i < 2 * N; ++i)if(k[i] && abs(ans) > max(i, N) - min(i, N))ans = static_cast<long>(i - N);

    string answerstring;
    for(long p = W - 1, q = H - 1, now = ans; p || q; ){
        now -= n[p][q];
        if(p && dp[p - 1][q][now + N]){
            answerstring.push_back('S');
            --p;
        }else{
            answerstring.push_back('E');
            --q;
        }
    }
    reverse(answerstring.begin(), answerstring.end());
    cout << answerstring << endl;
    return 0;
}

Battle History