SHARE
TWEET

Untitled

a guest Apr 1st, 2017 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for(auto i=a; i<=b; ++i)
  4. #define REP(i, a, b) for(auto i=a; i<b; ++i)
  5. #define FORI(i, a, b) for(auto i=a; i!=b+1-2*(a>b); i+=1-2*(a>b))
  6. #define REPI(i, a, b) for(auto i=a-(a>b); i!=b-(a>b); i+=1-2*(a>b))
  7. #define ALL(v) v.begin(),v.end()
  8. #define mp(a, b) make_pair(a, b)
  9. #define pb(a) push_back(a)
  10. #define pf(a) push_front(a)
  11. #define eb(a, b) emplace_back(a, b)
  12. #define fir first
  13. #define sec second
  14. #define what_is(x) cout<<#x<<" is "<<x<<endl;
  15. #define type(x) typeid(x).name()
  16. #define ms(arr, val) memset(arr, val, sizeof(arr))
  17. #define min3(a,b,c) min(min(a,b),c)
  18. #define max3(a,b,c) max(max(a,b),c)
  19.  
  20. using namespace std;
  21.  
  22. int dp_solve[110][110][110];
  23.  
  24.  
  25. class CheeseSlicing
  26. {
  27.     public:
  28.         int totalArea(int A, int B, int C, int S)
  29.         {
  30.             ms(dp_solve, -1);
  31.             return solve(A, B, C, S);
  32.         }
  33.  
  34.         int solve(int A, int B, int C, int S)
  35.         {
  36.             int max_1 = max3(A, B, C), max_2 = 0, minim = min3(A, B, C);
  37.            
  38. //            cout<<A<<" "<<B<<" "<<C<<endl;
  39.             if(minim < S)
  40.                 return 0;
  41.  
  42.             if(A == max_1)
  43.                 max_2 = max(B, C);
  44.  
  45.             else if(B == max_1)
  46.                 max_2 = max(A, C);
  47.  
  48.             else if(C == max_1)
  49.                 max_2 = max(A, B);
  50.            
  51.             int &ret = dp_solve[A][B][C];
  52.            
  53.             if(ret != -1)
  54.                 return ret;
  55.                
  56.             ret = max_1 * max_2;
  57.            
  58.             FOR(i, 1, A-1)
  59.                 ret = max(ret, solve(i, B, C, S) + solve(A-i, B, C, S));
  60.            
  61.             FOR(i, 1, B-1)
  62.                 ret = max(ret, solve(A, i, C, S) + solve(A, B-i, C, S));
  63.            
  64.             FOR(i, 1, C-1)
  65.                 ret = max(ret, solve(A, B, i, S) + solve(A, B, C-i, S));
  66.        
  67.             return ret;
  68.         }
  69. };
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