437 - The Tower of Babylon Solution

437 - The Tower of Babylon Solution

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

class dimension{
public:
int x;
int y;
int z;
};

bool area_sort(dimension d1, dimension d2){
if ((d1.x * d1.y) > (d2.x * d2.y))
return true;
return false;
}

int calculate_max_height(vector<dimension>&vec){
int max = 0, *height, len=vec.size(), i,j,sum;
dimension d1,d2;
height = new int[len];
for (i = 0; i < len; i++){
height[i] = vec[i].z;
}
max = height[0];

for (i = 1;i < len; i++){
d1 = vec[i];
for (j = 0; j < i; j++){
d2 = vec[j];
if (d1.x < d2.x && d1.y < d2.y){
sum = d1.z + height[j];
if (sum > height[i]){
height[i] = sum;
if (sum > max)
max = sum;
}
}
}
}
return max;
}

int main(){
vector<dimension>vec;
dimension d[90];
int n,i,k,x,y,z,temp,test_case=1;
while (cin >> n){
if (n == 0)
break;
for (i = 0; i < n; i++){
cin >> x >> y >> z;
k = 3 * i;
d[k].x = x;
d[k].y = y;
d[k].z = z;
if (d[k].x>d[k].y){
temp = d[k].x;
d[k].x = d[k].y;
d[k].y = temp;
}
vec.push_back(d[k]);
k++;
d[k].x = y;
d[k].y = z;
d[k].z = x;
if (d[k].x>d[k].y){
temp = d[k].x;
d[k].x = d[k].y;
d[k].y = temp;
}
if (!(d[k - 1].x == d[k].x && d[k - 1].y == d[k].y))
vec.push_back(d[k]);
k++;
d[k].x = z;
d[k].y = x;
d[k].z = y;
if (d[k].x>d[k].y){
temp = d[k].x;
d[k].x = d[k].y;
d[k].y = temp;
}
if (!(d[k - 1].x == d[k].x && d[k - 1].y == d[k].y))
vec.push_back(d[k]);
}
sort(vec.begin(), vec.end(), area_sort);
cout <<"Case "<<test_case++<<": "<<"maximum height = "<< calculate_max_height(vec) << endl;

vec.clear();
}
return 0;
}