3VXoG3 - Online C++0x Compiler & Debugging Tool

#include<bits/stdc++.h>
#define f1(i, n) for(ll i=1;i<=n;++i)
#define f0(i, n) for(ll i=0;i<n;++i)
#define ull unsigned long long
#define ll long long
#define rev(a) reverse(a.begin(),a.end())
#define all(x) x.begin(),x.end()
#define so(A, n) sort(A+1, A+n+1)
using namespace std;
const int N = 1e6;
ll a[1002][1002], f[1002][1002], t[1002][1002], r2[1002];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= m; i++) f[i][1] = a[i][1];
    for (int j = 2; j <= n; j++) {
        for (int i = 1; i <= m; i++) {
            ll mx = f[i][j - 1]; t[i][j] = i;
            if (i > 1 && f[i - 1][j - 1] > mx) { mx = f[i - 1][j - 1]; t[i][j] = i - 1; }
            if (i < m && f[i + 1][j - 1] > mx) { mx = f[i + 1][j - 1]; t[i][j] = i + 1; }
            f[i][j] = mx + a[i][j];
        }
    }

    ll R = LLONG_MIN;
    int x = 0;
    for (int i = 1; i <= m; i++) if (f[i][n] > R) { R = f[i][n]; x = i; }
    int y = n;
    while (y >= 1) { r2[y] = x; x = t[x][y]; y--; }
    cout << R << "\n";
    for (int j = 1; j <= n; j++) cout << r2[j] << " " << j << "\n";

    return 0;
}