Advertisement
i_love_rao_khushboo

Untitled

Jul 31st, 2022
1,089
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.99 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define pb push_back
  8. #define ppb pop_back
  9. #define pf push_front
  10. #define ppf pop_front
  11. #define mp make_pair
  12. #define F first
  13. #define S second
  14. #define PI 3.1415926535897932384626
  15. #define sz(x) ((int)(x).size())
  16. #define vset(v, n, val) v.clear(); v.resize(n, val)
  17.  
  18. typedef pair<int, int> pii;
  19. typedef pair<ll, ll> pll;
  20. typedef vector<int> vi;
  21. typedef vector<ll> vll;
  22. typedef vector<ull> vull;
  23. typedef vector<bool> vb;
  24. typedef vector<char> vc;
  25. typedef vector<string> vs;
  26. typedef vector<pii> vpii;
  27. typedef vector<pll> vpll;
  28. typedef vector<vi> vvi;
  29. typedef vector<vll> vvll;
  30. typedef vector<vull> vvull;
  31. typedef vector<vb> vvb;
  32. typedef vector<vc> vvc;
  33. typedef vector<vs> vvs;
  34.  
  35. /************************************************** DEBUGGER *******************************************************************************************************/
  36.  
  37. #ifndef ONLINE_JUDGE
  38. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  39. #else
  40. #define debug(x)
  41. #endif
  42.  
  43. void _print(ll t) { cerr << t; }
  44. void _print(int t) { cerr << t; }
  45. void _print(string t) { cerr << t; }
  46. void _print(char t) { cerr << t; }
  47. void _print(ld t) { cerr << t; }
  48. void _print(double t) { cerr << t; }
  49. void _print(ull t) { cerr << t; }
  50.  
  51. template <class T, class V> void _print(pair <T, V> p);
  52. template <class T> void _print(vector <T> v);
  53. template <class T> void _print(vector <vector<T>> v);
  54. template <class T> void _print(set <T> v);
  55. template <class T, class V> void _print(map <T, V> v);
  56. template <class T> void _print(multiset <T> v);
  57. template <class T, class V> void _print(multimap <T, V> v);
  58. template <class T> void _print(queue <T> v);
  59. template <class T> void _print(priority_queue <T> v);
  60. template <class T> void _print(stack <T> s);
  61.  
  62. // modify it's definition below as per need such as it can be used for STL containers with custom args passed
  63. template <class T> void _print(T v);
  64.  
  65. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  66. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  67. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  68. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  69. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  70. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  71. template <class T, class V> void _print(multimap <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  72. template <class T> void _print(queue <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.front()); v.pop(); cerr << " "; } cerr << "]"; }
  73. template <class T> void _print(priority_queue <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.top()); v.pop(); cerr << " "; } cerr << "]"; }
  74. template <class T> void _print(stack <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.top()); v.pop(); cerr << " "; } cerr << "]"; }
  75. template <class T> void _print(T v) {  }
  76.  
  77. /*******************************************************************************************************************************************************************/
  78.  
  79. const int INF = 1e8;
  80. const int mod = 1e9+7;
  81.  
  82. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  83.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  84.                          
  85. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  86. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  87.  
  88. /******************************************************************************************************************************/
  89.  
  90. vi dx = {-1, 0, 1, 0};
  91. vi dy = {0, 1, 0, -1};
  92.  
  93. bool is_valid(int x, int y, int n, int m, vvi &v) {
  94.     return ((x >= 0) and (x < n) and (y >= 0) and (y < m) and (v[x][y] != -1));
  95. }
  96.  
  97. int helper_2(int i, int j, int n, int m, vvi &v, vvi &dp_2) {
  98.     // base case(s)
  99.     if((i == 0) and (j == 0)) {
  100.         if(v[i][j] == -1) return -INF;
  101.         else if(v[i][j] == 0) return 0;
  102.         else return 1;
  103.     }
  104.  
  105.     if(v[i][j] == -1) return -INF;
  106.    
  107.     // check if already calculated or not
  108.     if(dp_2[i][j] != -1) return dp_2[i][j];
  109.    
  110.     int res = -INF, curr_cell_contri = 0;
  111.     bool flag = 0;
  112.  
  113.     if(v[i][j] == 1) {
  114.         flag = 1;
  115.         curr_cell_contri = 1;
  116.         v[i][j] = 0;
  117.     }
  118.  
  119.     for(int d = 0; d < 4; d++) {
  120.         if((d == 1) or (d == 2)) continue;
  121.  
  122.         int nx = i + dx[d], ny = j + dy[d];
  123.         if(!is_valid(nx, ny, n, m, v)) continue;
  124.  
  125.         int tmp_ans = helper_2(nx, ny, n, m, v, dp_2);
  126.         if(tmp_ans != -INF) tmp_ans += curr_cell_contri;
  127.  
  128.         res = max(res, tmp_ans);
  129.     }
  130.  
  131.     if(flag) v[i][j] = 1;
  132.  
  133.     return dp_2[i][j] = res;
  134. }
  135.  
  136. int helper_1(int i, int j, int n, int m, vvi &v, vvi &dp_1, vvi &dp_2) {
  137.     // base case(s)
  138.     if((i == n - 1) and (j == m - 1)) {
  139.         if(v[i][j] == -1) return -INF;
  140.         else return helper_2(i, j, n, m, v, dp_2);
  141.     }
  142.  
  143.     if(v[i][j] == -1) return -INF;
  144.    
  145.     // check if already calculated or not
  146.     if(dp_1[i][j] != -1) return dp_1[i][j];
  147.    
  148.     int res = -INF, curr_cell_contri = 0;
  149.     bool flag = 0;
  150.  
  151.     if(v[i][j] == 1) {
  152.         flag = 1;
  153.         curr_cell_contri = 1;
  154.         v[i][j] = 0;
  155.     }
  156.  
  157.     for(int d = 0; d < 4; d++) {
  158.         if((d == 0) or (d == 3)) continue;
  159.  
  160.         int nx = i + dx[d], ny = j + dy[d];
  161.         if(!is_valid(nx, ny, n, m, v)) continue;
  162.        
  163.         int tmp_ans = helper_1(nx, ny, n, m, v, dp_1, dp_2);
  164.         if(tmp_ans != -INF) tmp_ans += curr_cell_contri;
  165.  
  166.         res = max(res, tmp_ans);
  167.     }
  168.  
  169.     if(flag) v[i][j] = 1;
  170.    
  171.     return dp_1[i][j] = res;
  172. }
  173.  
  174. int cherry_pickup(vvi &v) {
  175.     int n = sz(v);
  176.     if(n == 0) return 0;
  177.    
  178.     int m = sz(v[0]);
  179.    
  180.     vvi dp_1(n, vi(m, -1)), dp_2(n, vi(m, -1));
  181.    
  182.     int res = helper_1(0, 0, n, m, v, dp_1, dp_2);
  183.     if(res == -INF) res = 0;
  184.    
  185.     return res;
  186. }
  187.  
  188. void solve()
  189. {
  190.     int n, m; cin >> n >> m;
  191.     vvi v(n, vi(m));
  192.    
  193.     for(int i = 0; i < n; i++) {
  194.         for(int j = 0; j < m; j++) cin >> v[i][j];
  195.     }
  196.    
  197.     cout << cherry_pickup(v) << "\n";
  198. }
  199.  
  200. int main()
  201. {
  202.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  203.  
  204.     // #ifndef ONLINE_JUDGE
  205.     //     freopen("input.txt", "r", stdin);
  206.     //     freopen("output.txt", "w", stdout);
  207.     // #endif
  208.    
  209.     // #ifndef ONLINE_JUDGE
  210.     //      freopen("error.txt", "w", stderr);
  211.     // #endif
  212.    
  213.     int t = 1;
  214.     // int test = 1;
  215.     // cin >> t;
  216.     while(t--) {
  217.         // cout << "Case #" << test++ << ": ";
  218.         solve();
  219.     }
  220.  
  221.     return 0;
  222. }
  223.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement