Submission by @naan112358

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

namespace Naan {
    int main(unsigned long W, unsigned long H) {
        constexpr unsigned long N = 6500;
        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;
    }

    int main_three(unsigned long W, unsigned long H){
        vector<string> orya({"EESS", "ESES", "ESSE", "SEES", "SENESS", "SESE", "SSENNESS", "SSENES", "SSEE", "EESWWSEE", "ESWSEE", "EESWSE"});
        vector<vector<long>> n(W, vector<long>(H));
        for (auto &i : n)for (auto &j : i)cin >> j;

        auto f = [&n](const string& s){
            auto ret = n[0][0];
            auto i = 0, j = 0;
            for(const auto& c : s){
                if(c == 'E')++j;
                if(c == 'S')++i;
                if(c == 'W')--j;
                if(c == 'N')--i;
                ret += n[i][j];
            }
            return abs(ret);
        };

        unsigned long ans{numeric_limits<unsigned long>::max()};
        string answerstring;
        for(const auto& s : orya){
            auto k = f(s);
            if(ans > k){
                ans = k;
                answerstring = s;
            }
        }
        cout << answerstring << endl;
        return 0;
    }
}

int main(){
    unsigned long H, W;
    cin >> H >> W;
    if(H == 3){
        Naan::main_three(H, W);
    }else{
        Naan::main(H, W);
    }
}

Battle History