fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Box
  5. {
  6.     int l;
  7.     int w;
  8.     int h;
  9. };
  10.  
  11. int compare(const void* a, const void* b)
  12. {
  13.     return ((*(Box *)b).l)*((*(Box *)b).w) - ((*(Box *)a).l)*((*(Box *)a).w);
  14. }
  15.  
  16. int maxBoxHeight(Box arr[], int n)
  17. {
  18.     Box rot[3*n];
  19.     int temp;
  20.     int r=0;
  21.  
  22.     for(int i=0; i<n; i++)
  23.     {
  24.         rot[r] = arr[i];
  25.         r++;
  26.  
  27.         rot[r].h = arr[i].l;
  28.         rot[r].l = max(arr[i].w, arr[i].h);
  29.         rot[r].w = min(arr[i].w, arr[i].h);
  30.         r++;
  31.  
  32.         rot[r].h = arr[i].w;
  33.         rot[r].l = max(arr[i].l, arr[i].h);
  34.         rot[r].w = min(arr[i].l, arr[i].h);
  35.         r++;
  36.     }
  37.  
  38.     n = 3*n;
  39.     qsort(rot, n, sizeof(rot[0]), compare);
  40.  
  41.     int tab[n];
  42.     int res[n];
  43.  
  44.     for(int i=0; i<n; i++)
  45.         tab[i] = rot[i].h, res[i] = -1;
  46.  
  47.     for(int i=1; i<n; i++)
  48.     {
  49.         for(int j=0; j<i; j++)
  50.         {
  51.             if(rot[i].l < rot[j].l && rot[i].w < rot[j].w && tab[j] + rot[i].h > tab[i])
  52.             {
  53.                 tab[i] = tab[j] + rot[i].h;
  54.                 res[i] = j;
  55.             }
  56.         }
  57.     }
  58.  
  59.     int k=n-1;
  60.     while(k != -1)
  61.     {
  62.         printf("%2d x %2d x %2d\n", rot[k].l, rot[k].w, rot[k].h);
  63.         k = res[k];
  64.     }
  65.  
  66.     return tab[n-1];
  67. }
  68.  
  69. int main()
  70. {
  71.     Box arr[] = { {7, 6, 4}, {3, 2, 1}, {6, 5, 4}, {32, 12, 10} };
  72.     int n = sizeof(arr)/sizeof(arr[0]);
  73.  
  74.     printf("\nMax Box(Stack) Height: %d\n", maxBoxHeight(arr, n));
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 2 x  1 x  3
 3 x  2 x  1
 5 x  4 x  6
 6 x  5 x  4
 7 x  6 x  4
12 x 10 x 32
32 x 12 x 10

Max Box(Stack) Height: 60
https://ideone.com/j2TklH
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!