Equilateral numbers

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const ll MAX_LEN = (1e6 + 1234) * 2;
 
ll numbers[MAX_LEN];
 
signed main() {
	ll n;
	cin >> n;
 
	for (ll i = 0; i < MAX_LEN; i++) {
		numbers[i] = ((i + 1) * (i + 2)) / 2;
	}
	assert(numbers[MAX_LEN - 1] > n);
 
	for (ll i = 0; i < MAX_LEN; i++) {
		if (numbers[i] == n) {
			cout << 1 << '\n';
			return 0;
		}
	}
 
	for (ll i = 0; i < MAX_LEN; i++) {
		if (numbers[i] > n) break;
		auto it = lower_bound(numbers, numbers + MAX_LEN, n - numbers[i]);
		if ((numbers[i] + (*it)) == n) {
			cout << 2 << '\n';
			return 0;
		}
	}
 
	cout << 3 << '\n';
 
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED