Implementation 1: Using vector Implementation 2: Using multiset Edit with LiveUpdate

CSES - Towers

Authors: Benjamin Qi, Danh Ta Chi Thanh

Appears In

Implementation 1: Using vector Implementation 2: Using multiset

Time Complexity: $\mathcal{O}(N\log N)$

Greedy approach: always add the next cube on top of the tower with the smallest possible cube (or create a new tower if this isn't possible).

Equivalent to longest non-decreasing subsequence!

C++

Implementation 1: Using `vector`

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;

Implementation 2: Using `multiset`

#include <bits/stdc++.h>
using namespace std;

multiset<int> ans; int n,k;
 
void solve(){
	cin >> n;
	for (int i=0;i<n;++i){
		cin >> k;
		auto it = ans.upper_bound(k);

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!