OIG II - cia (Alt)

#include <bits/stdc++.h>

#define int long long

constexpr int sizik = 50 * 1001;

int a[sizik];
int a_size = 0;
int ost[sizik];
int curr = 2, idx = 3;
int wynik = 0, prev_znane = 0, prev_wynik = 0;
int znane = 0;
int n;

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n;

    a[a_size++] = 1;
    a[a_size++] = 2;
    a[a_size++] = 2;
    while ((int)a_size < 30000) {
        for (int i = 0; i < a[curr]; i++) {
            a[a_size++] = idx;
        }
        curr++, idx++;
    }

    idx = 1;
    while (znane < n) {
        prev_znane = znane;
        prev_wynik = wynik;
        ost[idx] = ost[idx - 1] + a[idx - 1];
        znane += idx * ((((ost[idx] + 1) * ost[idx]) - (ost[idx - 1] * (ost[idx - 1] + 1))) >> 1);
        wynik += idx * a[idx - 1];

        idx++;
    }
    idx--;

    int c = ost[idx - 1] + 1, c1 = 0;
    while (prev_znane < n) {
        prev_znane += c;
        c1++;
        if (c1 == idx) {
            c1 = 0, c++;
        }
        prev_wynik++;
    }

    std::cout << prev_wynik << '\n';
    return 0;
}