SHARE
TWEET

OII Discesa

informaticage Jan 24th, 2020 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.     OII Training 2020 - UnivAQ
  3.     Author: Samuel Finocchio
  4.     Date: 24/01/2020
  5.     Name: discesa
  6.     Link: https://training.olinfo.it/#/task/discesa
  7.     Description:
  8.     Solved using simple recursion
  9. **/
  10. #include <iostream>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. int solve ( const vector<vector<int>> &piramid );
  16. int solve ( const vector<vector<int>> &piramid, int i, int j );
  17.  
  18. int main( void )
  19. {
  20.     /// IO From file
  21.     freopen ("input.txt","r", stdin );
  22.     freopen ("output.txt","w", stdout);
  23.  
  24.     int N;
  25.     cin >> N;
  26.  
  27.     /// Matrix initialized with -1 everywhere
  28.     vector <vector<int>> piramid ( N, vector<int>( N, -1 ) );
  29.  
  30.     /// Reading input
  31.     for ( int i = 0; i < N; i++ )
  32.         for ( int j = 0; j <= i; j++ )
  33.             cin >> piramid [ i ][ j ];
  34.  
  35.     /// Calling helper function
  36.     cout << solve ( piramid );
  37.     return 0;
  38. }
  39.  
  40. int solve ( const vector<vector<int>> &piramid ) {
  41.     return solve ( piramid, 0, 0 );
  42. }
  43.  
  44. int solve ( const vector<vector<int>> &piramid, int i, int j ) {
  45.     /// Exiting on outofbound or on -1
  46.     if ( i < 0 || i >= piramid.size() )
  47.         return 0;
  48.     if ( j < 0 || j >= piramid.size() )
  49.         return 0;
  50.     if ( piramid [i][j] == -1 )
  51.         return 0;
  52.  
  53.     /// Returning the maximum between left and right side
  54.     int res = piramid[i][j] +
  55.         max (
  56.             solve ( piramid, i + 1, j    ),
  57.             solve ( piramid, i + 1, j + 1)
  58.         );
  59.  
  60.     /// Uncomment to watch recursion
  61.     // cout << "( " << i << ", " << j << " ) -> " << res << endl;
  62.     return res;
  63. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top