Die hard - nerdarena

/// Complexitate O(n^2). Sper sa dea bine
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("diehard.in");
ofstream cout("diehard.out");
#define from mat /// Fara asta -> memory limit.
const int inf = 1e9, mxN = 1e3;
short mat[mxN+1][mxN+1], pozTop[mxN+1], pozBottom[mxN+1];;
int dp[mxN+1][mxN+1], top[mxN+2], bottom[mxN+2];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin >> mat[i][j];
    /// Cazuri de baza.
    for(int i = 1;i<=n;i++)
        dp[i][1] = mat[i][1];
    for(int i = 1;i<=n;i++)
        for(int j = 2;j<=m;j++)
            dp[i][j] = inf;

    /// Completeam restul dinamicii.
    /// Ideea este ca un caz in care mergem mai intai
    /// intr-o directie si apoi invers nu poate fi optim. ( sus -> jos)

    for(int j = 2;j<=m;j++)
    {
        ///Resetam tablourile top si bottom.
        for(int i = 1;i<=n;i++)
            top[i] = bottom[i] = inf, pozTop[i] = pozBottom[i] = -1;
        /// Calculam top.
        pozTop[1] = 1;
        top[1] = mat[1][j] + dp[1][j-1];
        for(int i = 2;i<=n;i++)
        {
            int A = top[i-1] + mat[i][j];
            int B = mat[i][j] + dp[i][j-1];
            if(A < B) pozTop[i] = pozTop[i-1];
            else pozTop[i] = i;
            top[i] = min(A,B);
        }
        /// Calculam bottom.
        pozBottom[n] = n;
        bottom[n] = mat[n][j] + dp[n][j-1];
        for(int i = n - 1; i > 0; i--)
        {
            int A = bottom[i+1] + mat[i][j];
            int B = mat[i][j] + dp[i][j-1];
            if(A < B) pozBottom[i] = pozBottom[i+1];
            else pozBottom[i] = i;
            bottom[i] = min(A,B);
        }
        /// Folosind vectorii top si bottom construim coloana j de dp.
        for(int i = 1;i<=n;i++)
        {
            int A = dp[i][j-1] + mat[i][j] , B = top[i], C = bottom[i];
            if(A < B && A < C)
                from[i][j] = i;
            else if(B < A && B < C)
                from[i][j] = pozTop[i];
            else from[i][j] = pozBottom[i];
            dp[i][j] = min(A, min(B,C));
        }
    }
    int pozX = -1, pozY = m;
    int sol = 2e9;
    for(int i = 1;i<=n;i++)
    {
        if(dp[i][m] < sol)
            sol = dp[i][m], pozX = i;
    }
    /// Reconstruim traseul
    string traseu = ""; int linieStart = -1;
    while(pozY > 1)
    {
        if(pozY == 2) linieStart = from[pozX][pozY];
        //cout << from[pozX][pozY] << ' ' ;
        int next_line = from[pozX][pozY];
        while(pozX != next_line)
        {
            if(pozX > next_line)
                traseu+='S', pozX--;
            else traseu+='N', pozX++;
        }
        traseu+='E';
        pozY--;
    }
    reverse(traseu.begin(),traseu.end());
    cout << sol << '\n' << linieStart << ' ' << traseu;
}