# PROBLEM LINK: Tallest Tower | CodeChef

# Problem Code: Tallest Tower | CodeChef

# Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef

# Contest : Internal Contest CodeChef Adgitm Coding Competition | CodeChef

* Author:* Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

*Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9*

**Tester:***Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9*

**Editorialist:**# DIFFICULTY:

Easy-Med

# PROBLEM:

You are a kid playing with rectangle blocks with sides of length xx and yy and height of 1 unit. Your friend gives you n blocks one by one. You can either accept the block or reject it. You want to stack the blocks such that the blocks form a tall tower. While stacking the blocks you make sure to only accept the block if and only if the block is smaller than the block on top right now. A block is smaller if it fits inside the boundaries of the block currently on top (i.e. doesnâ€™t stick out)

**NOTE: You can always reject a block if you want**

**NOTE: You always stack the blocks such that the height of the tower increases by 1 unit every time**

You need to find the maximum height of the tower possible if you already know the blocks which your friend is going to give you and in which order.

# SOLUTION:

C++:

int n;

vector<pair<int, int>> arr(1000);

const int MAX = 1005;

vector<vector> memo(MAX, vector(MAX, -1));

int rec(int i, int prev) {

if (i >= n) return 0;

if (memo[i][prev] != -1) {

return memo[i][prev];

}

// check if current rect can be put on top or not

int s1 = arr[prev].first;

int s2 = arr[prev].second;

int p1 = arr[i].first;

int p2 = arr[i].second;

if (max(p1, p2) <= max(s1, s2) && min(p1, p2) <= min(s1, s2)) {

// possible

return memo[i][prev] = max(1 + rec(i + 1, i), rec(i + 1, prev));

} else {

return memo[i][prev] = rec(i + 1, prev);

}

}

int main() {

cin >> n;

for (int i = 0; i < n; i++) {

int a, b;

cin >> a >> b;

arr[i] = {a, b};

}

cout << rec(0, 0);

return 0;

}