#include<bits/stdc++.h>
using namespace std;
struct Box
{
int l;
int w;
int h;
};
int compare(const void* a, const void* b)
{
return ((*(Box *)b).l)*((*(Box *)b).w) - ((*(Box *)a).l)*((*(Box *)a).w);
}
int maxBoxHeight(Box arr[], int n)
{
Box rot[3*n];
int temp;
int r=0;
for(int i=0; i<n; i++)
{
rot[r] = arr[i];
r++;
rot[r].h = arr[i].l;
rot[r].l = max(arr[i].w, arr[i].h);
rot[r].w = min(arr[i].w, arr[i].h);
r++;
rot[r].h = arr[i].w;
rot[r].l = max(arr[i].l, arr[i].h);
rot[r].w = min(arr[i].l, arr[i].h);
r++;
}
n = 3*n;
qsort(rot, n, sizeof(rot[0]), compare);
int tab[n];
int res[n];
for(int i=0; i<n; i++)
tab[i] = rot[i].h, res[i] = -1;
for(int i=1; i<n; i++)
{
for(int j=0; j<i; j++)
{
if(rot[i].l < rot[j].l && rot[i].w < rot[j].w && tab[j] + rot[i].h > tab[i])
{
tab[i] = tab[j] + rot[i].h;
res[i] = j;
}
}
}
int k=n-1;
while(k != -1)
{
printf("%2d x %2d x %2d\n", rot[k].l, rot[k].w, rot[k].h);
k = res[k];
}
return tab[n-1];
}
int main()
{
Box arr[] = { {7, 6, 4}, {3, 2, 1}, {6, 5, 4}, {32, 12, 10} };
int n = sizeof(arr)/sizeof(arr[0]);
printf("\nMax Box(Stack) Height: %d\n", maxBoxHeight(arr, n));
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBCb3gKewogICAgaW50IGw7CiAgICBpbnQgdzsKICAgIGludCBoOwp9OwoKaW50IGNvbXBhcmUoY29uc3Qgdm9pZCogYSwgY29uc3Qgdm9pZCogYikKewogICAgcmV0dXJuICgoKihCb3ggKiliKS5sKSooKCooQm94ICopYikudykgLSAoKCooQm94ICopYSkubCkqKCgqKEJveCAqKWEpLncpOwp9CgppbnQgbWF4Qm94SGVpZ2h0KEJveCBhcnJbXSwgaW50IG4pCnsKICAgIEJveCByb3RbMypuXTsKICAgIGludCB0ZW1wOwogICAgaW50IHI9MDsKCiAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspCiAgICB7CiAgICAgICAgcm90W3JdID0gYXJyW2ldOwogICAgICAgIHIrKzsKCiAgICAgICAgcm90W3JdLmggPSBhcnJbaV0ubDsKICAgICAgICByb3Rbcl0ubCA9IG1heChhcnJbaV0udywgYXJyW2ldLmgpOwogICAgICAgIHJvdFtyXS53ID0gbWluKGFycltpXS53LCBhcnJbaV0uaCk7CiAgICAgICAgcisrOwoKICAgICAgICByb3Rbcl0uaCA9IGFycltpXS53OwogICAgICAgIHJvdFtyXS5sID0gbWF4KGFycltpXS5sLCBhcnJbaV0uaCk7CiAgICAgICAgcm90W3JdLncgPSBtaW4oYXJyW2ldLmwsIGFycltpXS5oKTsKICAgICAgICByKys7CiAgICB9CgogICAgbiA9IDMqbjsKICAgIHFzb3J0KHJvdCwgbiwgc2l6ZW9mKHJvdFswXSksIGNvbXBhcmUpOwoJCiAgICBpbnQgdGFiW25dOwogICAgaW50IHJlc1tuXTsKCiAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspCiAgICAgICAgdGFiW2ldID0gcm90W2ldLmgsIHJlc1tpXSA9IC0xOwoKICAgIGZvcihpbnQgaT0xOyBpPG47IGkrKykKICAgIHsKICAgICAgICBmb3IoaW50IGo9MDsgajxpOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBpZihyb3RbaV0ubCA8IHJvdFtqXS5sICYmIHJvdFtpXS53IDwgcm90W2pdLncgJiYgdGFiW2pdICsgcm90W2ldLmggPiB0YWJbaV0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRhYltpXSA9IHRhYltqXSArIHJvdFtpXS5oOwogICAgICAgICAgICAgICAgcmVzW2ldID0gajsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBpbnQgaz1uLTE7CiAgICB3aGlsZShrICE9IC0xKQogICAgewogICAgICAgIHByaW50ZigiJTJkIHggJTJkIHggJTJkXG4iLCByb3Rba10ubCwgcm90W2tdLncsIHJvdFtrXS5oKTsKICAgICAgICBrID0gcmVzW2tdOwogICAgfQoKICAgIHJldHVybiB0YWJbbi0xXTsKfQoKaW50IG1haW4oKQp7CiAgICBCb3ggYXJyW10gPSB7IHs3LCA2LCA0fSwgezMsIDIsIDF9LCB7NiwgNSwgNH0sIHszMiwgMTIsIDEwfSB9OwogICAgaW50IG4gPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKCiAgICBwcmludGYoIlxuTWF4IEJveChTdGFjaykgSGVpZ2h0OiAlZFxuIiwgbWF4Qm94SGVpZ2h0KGFyciwgbikpOwoKICAgIHJldHVybiAwOwp9Cg==