• API
• FAQ
• Tools
• Archive
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
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.
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.
Top