fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define endl "\n"
  4. #define F first
  5. #define S second
  6. #define loop(a,n) for(int i=a; i<=n ; i++)
  7. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  8. #define NAME ""
  9. using namespace std;
  10.  
  11. int a[1000][1000], g[1000][1000], trace[1000][1000];
  12. int n, res = 0, pos;
  13.  
  14. void nhap() {
  15.     cin >> n;
  16.     for(int i = 1; i <= n; ++i)
  17.         for(int j = 1; j <= i; ++j)
  18.             cin >> a[i][j];
  19. }
  20.  
  21. void solve() {
  22.     memset(g, 0, sizeof(g));
  23.     g[1][1] = a[1][1];
  24.     trace[1][1] = 0;
  25.  
  26.     for(int i = 2; i <= n; ++i) {
  27.         for(int j = 1; j <= i; ++j) {
  28.             if (g[i-1][j] > g[i-1][j-1]) {
  29.                 g[i][j] = g[i-1][j] + a[i][j];
  30.                 trace[i][j] = j;
  31.             } else {
  32.                 g[i][j] = g[i-1][j-1] + a[i][j];
  33.                 trace[i][j] = j - 1;
  34.             }
  35.         }
  36.     }
  37.  
  38.     for(int i = 1; i <= n; ++i) {
  39.         if (g[n][i] > res) {
  40.             res = g[n][i];
  41.             pos = i;
  42.         }
  43.     }
  44.  
  45.     cout << res << endl;
  46.  
  47.     int p[1000];
  48.     int row = n, col = pos;
  49.     while(row >= 1) {
  50.         p[row] = a[row][col];
  51.         col = trace[row][col];
  52.         row--;
  53.     }
  54.  
  55.     for(int i = 1; i <= n; ++i)
  56.         cout << p[i] << " ";
  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 9724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/wlCZTg
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!