#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; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter