hướng đông tây

#include <bits/stdc++.h>

using namespace std;
int n , m , a[1000][1000] , f[1000][1000] , maxx = -1;
void truyvet()
{
    vector <pair<int , int>> kq;
    int vx , vy = m , ii;
    for (int i = 1; i <= n; i++)
    if (f[i][m] > maxx)
    {
        vx = i;
        maxx = f[i][m];
    }
    ii = vx;
    cout << maxx << endl;
    while (vy > 1)
    {
        if (f[vx][vy - 1] > max(f[vx + 1][vy - 1] , f[vx - 1][vy - 1]))
        {
            vy--;
            kq.push_back({vx , vy});
        }
        if (f[vx - 1][vy - 1] > max(f[vx][vy - 1] , f[vx + 1][vy - 1]))
        {
            vx--;
            vy--;
            kq.push_back({vx , vy});
        }
        if (f[vx + 1][vy - 1] > max(f[vx - 1][vy - 1] , f[vx][vy - 1]))
        {
            vx++;
            vy--;
            kq.push_back({vx , vy});
        }
    }
    reverse (kq.begin() , kq.end());
    for (auto x : kq)
    cout << x.first << " " << x.second << endl;
    cout << ii << " " << m << endl;
}
int main()
{
    freopen ("f.inp" , "r" , stdin);
    freopen ("f.out" , "w" , stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
       for (int j = 1; j <= m; j++)
       cin >> a[i][j];
    memset (f , 0 , sizeof f);
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = max(f[i][j - 1] + a[i][j] , max(f[i + 1][j - 1] + a[i][j] , f[i - 1][j - 1] + a[i][j]));
    truyvet();
    return 0;
}