daily pastebin goal
82%
SHARE
TWEET

Twin robots

a guest Jan 30th, 2015 182 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <climits>
  4. #include <cstdlib>
  5. #include <cmath>
  6. #include <cctype>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <map>
  11. #include <set>
  12. #include <algorithm>
  13. #include <sstream>
  14. using namespace std;
  15.  
  16. typedef vector<int> vi;
  17. typedef vector<vi> vvi;
  18. typedef pair<int, int> ii;
  19. typedef vector<ii> vii;
  20. typedef vector<vii> vvii;
  21. typedef vector<bool> vb;
  22.  
  23. #define sz(c) int((c).size())
  24. #define all(c) (c).begin(), (c).end()
  25.  
  26. vvi grid;
  27. vector< vector< vector< vector<int> > > > memo;
  28. int n, x;
  29.  
  30. int sum(int i, int j, int k, int l,vector< vector< vector< vector<int> > > >& memo)
  31. {
  32.         if(memo[i][j][k][l] != INT_MIN)
  33.                 return memo[i][j][k][l];
  34.  
  35.         else
  36.         {
  37.                 int ans = grid[i][j] + grid[k][l], max = INT_MIN;
  38.                 if(i > 0 && l > 0)
  39.                 {
  40.                         int tmp = sum(i-1, j, k, l-1, memo);
  41.                         max = max < tmp ? tmp : max;
  42.                 }
  43.                 if(j > 0 && k > 0)
  44.                 {
  45.                         int tmp = sum(i, j-1, k-1, l, memo);
  46.                         max = max < tmp ? tmp : max;
  47.                 }
  48.                 return ans+max;
  49.         }
  50. }
  51.  
  52. int main(void)
  53. {
  54.         int n, x;
  55.         scanf("%d", &n);
  56.         grid.clear(); grid.resize(n);
  57.  
  58.         for(int i = 0;i < n;i++)
  59.         {
  60.                 for(int j = 0;j < n;j++)
  61.                 {
  62.                         scanf("%d", &x);
  63.                         grid[i].push_back(x);
  64.                 }
  65.         }
  66.         memo.clear(); memo.resize(n, vector< vector< vector<int> > >(n, vector< vector<int> >(n, vector<int>(n, INT_MIN))));
  67.         memo[0][0][0][n-1] = grid[0][0] + grid[0][n-1];
  68.  
  69.         int ans = sum(n-1, 0, n-1, n-1, memo);
  70.         printf("%d\n", ans);
  71. }
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