Advertisement
Josif_tepe

Untitled

Dec 1st, 2021
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int dp[105][105];
  6. int main()
  7. {
  8.     int n;
  9.     cin>>n;
  10.     int matrica[n][n];
  11.  
  12.  
  13.  
  14.     for(int i=0; i<n; i++){
  15.             for(int j=0; j<=i; j++){
  16.                 cin>>matrica[i][j];
  17.             }
  18.  
  19.     }
  20.  
  21.     for(int i=0; i<n; i++){
  22.         for(int j=0; j<n; j++){
  23.             dp[i][j]=-2e9;
  24.         }
  25.     }
  26.  
  27.     dp[0][0] = 0;
  28.  
  29.     for(int i=0; i<n; i++){
  30.         for(int j=0; j<=i; j++){
  31.             dp[i+1][j]=max(dp[i+1][j], dp[i][j]+matrica[i][j]);
  32.             if(j+1<=i + 1 ){
  33.             dp[i+1][j+1]=max(dp[i+1][j+1], dp[i][j]+matrica[i][j]);
  34.             }
  35.         }
  36.     }
  37.     int result=0;
  38.     for(int i=0; i<=n ; i++){
  39.         for(int j=0; j<=i; j++){
  40.         result=max(result, dp[i][j]);
  41.         }
  42.     }
  43.  
  44.     cout<<result;
  45.  
  46.     return 0;
  47. }
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement