Advertisement
Guest User

Untitled

a guest
Apr 1st, 2017
337
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.89 KB | None | 0 0
  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. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement