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 vi = vector<int>;
#define pb push_back
#define sz(x) (int)(x).size()

int n;
vi x; // stores cubes in non-decreasing order

Implementation 2: Using `multiset`

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

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	int n, k;
	cin >> n;
	multiset<int> ans; 
	for (int i=0;i<n;++i) {

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!