fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[1000][1000], g[1000][1000], trace[1000][1000];
  4. int m, n, res = 0, pos;
  5.  
  6. void nhap() {
  7.     cin >> m >> n;
  8.     for (int i = 1; i <= m; ++i)
  9.         for (int j = 1; j <= n; ++j)
  10.             cin >> a[i][j];
  11. }
  12.  
  13. void solve() {
  14.     memset(g, 0, sizeof(g));
  15.     for (int i = 1; i <= m; ++i) {
  16.         g[i][1] = a[i][1];
  17.         trace[i][1] = 0;
  18.     }
  19.  
  20.     for (int j = 2; j <= n; ++j) {
  21.         for (int i = 1; i <= m; ++i) {
  22.             int val = g[i][j-1];
  23.             int fr = i;
  24.  
  25.             if (i > 1 && g[i-1][j-1] > val) {
  26.                 val = g[i-1][j-1];
  27.                 fr = i - 1;
  28.             }
  29.             if (i < m && g[i+1][j-1] > val) {
  30.                 val = g[i+1][j-1];
  31.                 fr = i + 1;
  32.             }
  33.  
  34.             g[i][j] = val + a[i][j];
  35.             trace[i][j] = fr;
  36.         }
  37.     }
  38.  
  39.     for (int i = 1; i <= m; ++i) {
  40.         if (g[i][n] > res) {
  41.             res = g[i][n];
  42.             pos = i;
  43.         }
  44.     }
  45.     int p[1000];
  46.     int row = pos, col = n;
  47.     while (col >= 1) {
  48.         p[col] = row;
  49.         row = trace[row][col];
  50.         col--;
  51.     }
  52.  
  53.     for (int i = 1; i < n; ++i)
  54.         cout << p[i] << "-->";
  55.     cout << p[n]<< endl;
  56.     cout  << res << endl;
  57. }
  58.  
  59. int main() {
  60.     ios_base::sync_with_stdio(0);
  61.     cin.tie(0); cout.tie(0);
  62.     nhap();
  63.     solve();
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 9692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
102800
0
https://ideone.com/RPgFOF
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!