Advertisement
lodha1503

Untitled

Aug 24th, 2023
755
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define MOD1 1000000007
  6. #define MOD2 998244353
  7. #define NO cout << "NO" << endl
  8. #define YES cout << "YES" << endl
  9. ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  10. ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
  11. ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
  12. ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
  13. ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
  14. ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}
  15. void print(vector<int> &ans){for(auto x: ans) cout<<x<<" "; cout<<endl;}
  16.  
  17. // ========================================================================================================================================================================================================
  18. vector<int> nrow={1,0};
  19. vector<int> ncol={0,1};
  20.  
  21. void recursion(vector<vector<int>> &matrix,ll n ,ll m,ll i,ll j,ll &sum,ll &ans,vector<vector<int>> &visited)
  22. {
  23.  
  24.   if(i==n-1 && j==m-1)
  25.   {
  26.      
  27.     if(sum>ans)
  28.         ans=sum;
  29.     return;
  30.   }
  31.  
  32.   for(int k=0;k<2;k++)
  33.   {
  34.     ll delrow=i+nrow[k];
  35.     ll delcol=j+ncol[k];
  36.    
  37.     if(delrow<n && delrow>=0 && delcol>=0 && delcol<m)
  38.     {
  39.        
  40.         if(visited[delrow][delcol]==0)
  41.         {
  42.             visited[delrow][delcol]=1;
  43.             sum+=matrix[delrow][delcol];
  44.            
  45.             recursion(matrix,n,m,delrow,delcol,sum,ans,visited);
  46.            
  47.             visited[delrow][delcol]=0;
  48.             sum-=matrix[delrow][delcol];
  49.         }
  50.        
  51.     }
  52.        
  53.   }
  54. }
  55.  
  56. void solve()
  57. {
  58.   ll n,m;cin>>n>>m;
  59.   ll ans=0;
  60.   vector<vector<int>> matrix(n,vector<int>(m,0));
  61.   vector<vector<int>> visited(n,vector<int>(m,0));
  62.   for(int i=0;i<n;i++)
  63.   {
  64.     for(int j=0;j<m;j++)
  65.     {
  66.         int e;cin>>e;
  67.         matrix[i][j]=e;
  68.     }
  69.   }
  70.   ll sum=0;
  71.   recursion(matrix,n,m,0,-1,sum,ans,visited);
  72.   cout<<ans<<endl;
  73.  
  74.  
  75.  
  76. }
  77.  
  78.  
  79. int main()
  80. {
  81.     solve();
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement