Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define pb push_back
- #define MOD1 1000000007
- #define MOD2 998244353
- #define NO cout << "NO" << endl
- #define YES cout << "YES" << endl
- 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;}
- ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
- ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
- ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
- ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
- 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;}
- void print(vector<int> &ans){for(auto x: ans) cout<<x<<" "; cout<<endl;}
- // ========================================================================================================================================================================================================
- vector<int> nrow={1,0};
- vector<int> ncol={0,1};
- void recursion(vector<vector<int>> &matrix,ll n ,ll m,ll i,ll j,ll &sum,ll &ans,vector<vector<int>> &visited)
- {
- if(i==n-1 && j==m-1)
- {
- if(sum>ans)
- ans=sum;
- return;
- }
- for(int k=0;k<2;k++)
- {
- ll delrow=i+nrow[k];
- ll delcol=j+ncol[k];
- if(delrow<n && delrow>=0 && delcol>=0 && delcol<m)
- {
- if(visited[delrow][delcol]==0)
- {
- visited[delrow][delcol]=1;
- sum+=matrix[delrow][delcol];
- recursion(matrix,n,m,delrow,delcol,sum,ans,visited);
- visited[delrow][delcol]=0;
- sum-=matrix[delrow][delcol];
- }
- }
- }
- }
- void solve()
- {
- ll n,m;cin>>n>>m;
- ll ans=0;
- vector<vector<int>> matrix(n,vector<int>(m,0));
- vector<vector<int>> visited(n,vector<int>(m,0));
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<m;j++)
- {
- int e;cin>>e;
- matrix[i][j]=e;
- }
- }
- ll sum=0;
- recursion(matrix,n,m,0,-1,sum,ans,visited);
- cout<<ans<<endl;
- }
- int main()
- {
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement